{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Trapping Rain Water"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #array #two-pointers #dynamic-programming #monotonic-stack"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #数组 #双指针 #动态规划 #单调栈"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: trap"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #接雨水"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定&nbsp;<code>n</code> 个非负整数表示每个宽度为 <code>1</code> 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/10/22/rainwatertrap.png\" style=\"height: 161px; width: 412px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>height = [0,1,0,2,1,0,1,3,2,1,2,1]\n",
    "<strong>输出：</strong>6\n",
    "<strong>解释：</strong>上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 \n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>height = [4,2,0,3,2,5]\n",
    "<strong>输出：</strong>9\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == height.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 2 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>0 &lt;= height[i] &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [trapping-rain-water](https://leetcode.cn/problems/trapping-rain-water/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [trapping-rain-water](https://leetcode.cn/problems/trapping-rain-water/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[0,1,0,2,1,0,1,3,2,1,2,1]', '[4,2,0,3,2,5]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trapRainWater(self, heightMap: List[List[int]]) -> int:\n",
    "        m, n = len(heightMap), len(heightMap[0])\n",
    "        maxHeight = max(max(row) for row in heightMap)\n",
    "        water = [[maxHeight for _ in range(n)] for _ in range(m)]\n",
    "        dirs = [-1, 0, 1, 0, -1]\n",
    "\n",
    "        qu = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i == 0 or i == m - 1 or j == 0 or j == n - 1:\n",
    "                     if water[i][j] > heightMap[i][j]:\n",
    "                        water[i][j] = heightMap[i][j]\n",
    "                        qu.append([i, j])\n",
    "        \n",
    "        while len(qu) > 0:\n",
    "            [x, y] = qu.pop(0)\n",
    "            for i in range(4):\n",
    "                nx, ny = x + dirs[i], y + dirs[i + 1]\n",
    "                if nx < 0 or nx >= m or ny < 0 or ny >= n:\n",
    "                    continue\n",
    "                if water[x][y] < water[nx][ny] and water[nx][ny] > heightMap[nx][ny]:\n",
    "                    water[nx][ny] = max(water[x][y], heightMap[nx][ny])\n",
    "                    qu.append([nx, ny])\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                ans = ans + water[i][j] - heightMap[i][j]\n",
    "        return ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trapRainWater(self, heightMap: List[List[int]]) -> int:\n",
    "        # 接水先初始化边界，从边界开始层序遍历，\n",
    "        # 若边界高度 > 内部，说明该处可存水，同时将该处的高度替换，入堆\n",
    "        # 若边界高度 < 内部，无法存水，直接入堆\n",
    "        ans = 0\n",
    "        m, n = len(heightMap), len(heightMap[0])\n",
    "        visited = [[False] * n for _ in range(m)]\n",
    "        pq = []\n",
    "        for i in range(1, n - 1):\n",
    "            heapq.heappush(pq, (heightMap[0][i], 0, i))\n",
    "            heapq.heappush(pq, (heightMap[m-1][i], m-1, i))\n",
    "        for i in range(1, m - 1):\n",
    "            heapq.heappush(pq, (heightMap[i][0], i, 0))\n",
    "            heapq.heappush(pq, (heightMap[i][n-1], i, n-1))\n",
    "        while pq:\n",
    "            h, x, y = heapq.heappop(pq)\n",
    "            for dx, dy in [(-1,0),(1,0),(0,1),(0,-1)]:\n",
    "                nx, ny = x + dx, y + dy\n",
    "                if 0 < nx < m - 1 and 0 < ny < n - 1 and not visited[nx][ny]:\n",
    "                    visited[nx][ny] = True\n",
    "                    ans += max(0, h - heightMap[nx][ny])\n",
    "                    heapq.heappush(pq, (max(h, heightMap[nx][ny]), nx, ny))\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trapRainWater(self, heightMap: List[List[int]]) -> int:\n",
    "        n = len(heightMap)\n",
    "        m = len(heightMap[0])\n",
    "        maxheight = max(max(row) for row in heightMap)\n",
    "        water = [[maxheight for _ in range(m)] for _ in range(n)]\n",
    "        qu = []\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if i==0 or j==0 or i==n-1 or j==m-1:\n",
    "                    water[i][j] = heightMap[i][j]\n",
    "                    qu.append([i,j])\n",
    "\n",
    "        direct = [-1,0,1,0,-1]\n",
    "\n",
    "        while len(qu)>0:\n",
    "            i,j = qu.pop(0)\n",
    "            for k in range(4):\n",
    "                ni = i+direct[k]\n",
    "                nj = j+direct[k+1]\n",
    "                if ni<0 or ni>=n or nj<0 or nj>=m:\n",
    "                    continue\n",
    "                if water[ni][nj]>water[i][j]:\n",
    "                    water[ni][nj] = max(min(water[ni][nj], water[i][j]), heightMap[ni][nj])\n",
    "                    qu.append([ni,nj])\n",
    "        \n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                res+= water[i][j]-heightMap[i][j]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trapRainWater(self, heightMap: List[List[int]]) -> int:\n",
    "        m, n = len(heightMap), len(heightMap[0])\n",
    "        maxHeight = max(max(row) for row in heightMap)\n",
    "        water = [[maxHeight for _ in range(n)] for _ in range(m)]\n",
    "        dirs = [-1, 0, 1, 0, -1]\n",
    "\n",
    "        qu = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i == 0 or i == m - 1 or j == 0 or j == n - 1:\n",
    "                     if water[i][j] > heightMap[i][j]:\n",
    "                        water[i][j] = heightMap[i][j]\n",
    "                        qu.append([i, j])\n",
    "        \n",
    "        while len(qu) > 0:\n",
    "            [x, y] = qu.pop(0)\n",
    "            for i in range(4):\n",
    "                nx, ny = x + dirs[i], y + dirs[i + 1]\n",
    "                if nx < 0 or nx >= m or ny < 0 or ny >= n:\n",
    "                    continue\n",
    "                if water[x][y] < water[nx][ny] and water[nx][ny] > heightMap[nx][ny]:\n",
    "                    water[nx][ny] = max(water[x][y], heightMap[nx][ny])\n",
    "                    qu.append([nx, ny])\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                ans = ans + water[i][j] - heightMap[i][j]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def trapRainWater(self, heightMap):\n",
    "        if not heightMap or not heightMap[0]:\n",
    "            return 0\n",
    "        \n",
    "        import heapq    \n",
    "        m, n = len(heightMap), len(heightMap[0])\n",
    "        heap = []\n",
    "        visited = [[0]*n for _ in range(m)]\n",
    "\n",
    "        # Push all the block on the border into heap\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i == 0 or j == 0 or i == m-1 or j == n-1:\n",
    "                    heapq.heappush(heap, (heightMap[i][j], i, j))\n",
    "                    visited[i][j] = 1\n",
    "        \n",
    "        result = 0\n",
    "        while heap:\n",
    "            height, i, j = heapq.heappop(heap)    \n",
    "            for x, y in ((i+1, j), (i-1, j), (i, j+1), (i, j-1)):\n",
    "                if 0 <= x < m and 0 <= y < n and not visited[x][y]:\n",
    "                    result += max(0, height-heightMap[x][y])\n",
    "                    heapq.heappush(heap, (max(heightMap[x][y], height), x, y))\n",
    "                    visited[x][y] = 1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trapRainWater(self, heightMap: List[List[int]]) -> int:\n",
    "        m, n = len(heightMap), len(heightMap[0])\n",
    "        visited = [[False] * n for _ in range(m)]\n",
    "\n",
    "        heap = []\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i == 0 or i == m-1 or j == 0 or j == n-1:\n",
    "                    visited[i][j] = True\n",
    "                    heapq.heappush(heap, (heightMap[i][j], i, j))\n",
    "\n",
    "        res = 0\n",
    "        while heap:\n",
    "            height, x, y = heapq.heappop(heap)\n",
    "            for z in [1, -1]:\n",
    "                if 0 <= x + z < m and not visited[x+z][y]:\n",
    "                    if heightMap[x+z][y] <= height:\n",
    "                        res += height - heightMap[x+z][y]\n",
    "                    heapq.heappush(heap, (max(height, heightMap[x+z][y]), x+z, y))\n",
    "                    visited[x+z][y] = True\n",
    "                    \n",
    "                if 0 <= y + z < n and not visited[x][y+z]:\n",
    "                    if heightMap[x][y+z] <= height:\n",
    "                        res += height - heightMap[x][y+z]\n",
    "                    heapq.heappush(heap, (max(height, heightMap[x][y+z]), x, y+z))\n",
    "                    visited[x][y+z] = True\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trapRainWater(self, heightMap: List[List[int]]) -> int:\n",
    "        m, n = len(heightMap), len(heightMap[0])\n",
    "        visited = [[False] * n for _ in range(m)]\n",
    "        q = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i == 0 or i == m - 1 or j == 0 or j == n - 1:\n",
    "                    visited[i][j] = True\n",
    "                    heapq.heappush(q, (heightMap[i][j], i * n + j))\n",
    "        res = 0\n",
    "        dirs = [[-1, 0], [0, 1], [1, 0], [0, -1]]\n",
    "        while len(q) > 0:\n",
    "            height, position = heapq.heappop(q)\n",
    "            for dx, dy in dirs:\n",
    "                x1, y1 = (position // n) + dx, (position % n) + dy\n",
    "                # print(x1, y1)\n",
    "                if(x1 < 0 or x1 >= m or y1 < 0 or y1 >= n or visited[x1][y1]):\n",
    "                    continue\n",
    "                if height > heightMap[x1][y1]:\n",
    "                    res += height - heightMap[x1][y1]\n",
    "                visited[x1][y1] = True\n",
    "                heapq.heappush(q, (max(height, heightMap[x1][y1]), x1 * n + y1))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trapRainWater(self, heightMap: List[List[int]]) -> int:\n",
    "        if len(heightMap) <= 2 or len(heightMap[0]) <= 2:\n",
    "            return 0\n",
    "\n",
    "        m, n = len(heightMap), len(heightMap[0])\n",
    "        visited = [[0 for _ in range(n)] for _ in range(m)]\n",
    "        pq = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i == 0 or i == m - 1 or j == 0 or j == n - 1:\n",
    "                    visited[i][j] = 1\n",
    "                    heapq.heappush(pq, (heightMap[i][j], i * n + j))\n",
    "        \n",
    "        res = 0\n",
    "        dirs = [-1, 0, 1, 0, -1]\n",
    "        while pq:\n",
    "            height, position = heapq.heappop(pq)\n",
    "            for k in range(4):\n",
    "                nx, ny = position // n + dirs[k], position % n + dirs[k + 1]\n",
    "                if nx >= 0 and nx < m and ny >= 0 and ny < n and visited[nx][ny] == 0:\n",
    "                    if height > heightMap[nx][ny]:\n",
    "                        res += height - heightMap[nx][ny]\n",
    "                    visited[nx][ny] = 1    \n",
    "                    heapq.heappush(pq, (max(height, heightMap[nx][ny]), nx * n + ny))\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trapRainWater(self, heightMap: List[List[int]]) -> int:\n",
    "        if len(heightMap) <= 2 or len(heightMap[0]) <= 2:\n",
    "            return 0\n",
    "\n",
    "        m, n = len(heightMap), len(heightMap[0])\n",
    "        visited = [[0 for _ in range(n)] for _ in range(m)]\n",
    "        pq = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i == 0 or i == m - 1 or j == 0 or j == n - 1:\n",
    "                    visited[i][j] = 1\n",
    "                    heapq.heappush(pq, (heightMap[i][j], i * n + j))\n",
    "        \n",
    "        res = 0\n",
    "        dirs = [-1, 0, 1, 0, -1]\n",
    "        while pq:\n",
    "            height, position = heapq.heappop(pq)\n",
    "            for k in range(4):\n",
    "                nx, ny = position // n + dirs[k], position % n + dirs[k + 1]\n",
    "                if nx >= 0 and nx < m and ny >= 0 and ny < n and visited[nx][ny] == 0:\n",
    "                    if height > heightMap[nx][ny]:\n",
    "                        res += height - heightMap[nx][ny]\n",
    "                    visited[nx][ny] = 1    \n",
    "                    heapq.heappush(pq, (max(height, heightMap[nx][ny]), nx * n + ny))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trapRainWater(self, heightMap: List[List[int]]) -> int:\n",
    "        m, n = len(heightMap), len(heightMap[0])\n",
    "        if m<=2 or n<=2: return 0\n",
    "        visited = [[0 for _ in range(n)] for _ in range(m)] ### 标记已经更新过的点\n",
    "\n",
    "        pq = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i == 0 or i == m - 1 or j == 0 or j == n - 1: ### 先处理边界\n",
    "                    visited[i][j] = 1\n",
    "                    heapq.heappush(pq, (heightMap[i][j], i * n + j))\n",
    "\n",
    "        res = 0\n",
    "        dirs = [-1, 0, 1, 0, -1]\n",
    "        while pq:\n",
    "            height, position = heapq.heappop(pq)\n",
    "            for k in range(4):\n",
    "                nx, ny = position // n + dirs[k], position % n + dirs[k + 1]\n",
    "                if nx >= 0 and nx < m and ny >= 0 and ny < n and visited[nx][ny] == 0:\n",
    "                    if height > heightMap[nx][ny]: ### 即便 它周围没有被访问过的空白区域，高度比它小，但是这没有关系，能装，因为这是最外层的短板决定的\n",
    "                        res += height - heightMap[nx][ny]\n",
    "                    visited[nx][ny] = 1\n",
    "                    heapq.heappush(pq, (max(height, heightMap[nx][ny]), nx * n + ny))\n",
    "        return res\n",
    "                    \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from queue import PriorityQueue\n",
    "class Solution:\n",
    "    def trapRainWater(self, heightMap: List[List[int]]) -> int:\n",
    "        m = len(heightMap)\n",
    "        n = len(heightMap[0])\n",
    "        vis = [[False] * n for _ in range(m)]\n",
    "        direct = [[0, 1], [0, -1], [1, 0], [-1, 0]]\n",
    "        borderque = PriorityQueue()\n",
    "        for i in range(m):\n",
    "            borderque.put((heightMap[i][0], i, 0))\n",
    "            borderque.put((heightMap[i][n-1], i, n-1))\n",
    "            vis[i][0] = True\n",
    "            vis[i][n-1] = True\n",
    "        for j in range(1, n-1):\n",
    "            borderque.put((heightMap[0][j], 0, j))\n",
    "            borderque.put((heightMap[m-1][j], m-1, j))\n",
    "            vis[0][j] = True\n",
    "            vis[m-1][j] = True\n",
    "        maxhei = -inf\n",
    "        ans = 0\n",
    "        while borderque.empty() == False:\n",
    "            hei, x, y = borderque.get()\n",
    "            maxhei = max(maxhei, hei)\n",
    "            for i in range(4):\n",
    "                nx = x + direct[i][0]\n",
    "                ny = y + direct[i][1]\n",
    "                if nx >= 0 and nx < m and ny >= 0 and ny < n and not vis[nx][ny]:\n",
    "                    ans += max(0, maxhei - heightMap[nx][ny])\n",
    "                    borderque.put((heightMap[nx][ny], nx, ny))\n",
    "                    vis[nx][ny] = True\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "我们发现：装满水后水位最低的单元在边界上。我们找出所有的边界单元，然后搜索出高度最矮的边界单元，然后再基于其搜索其邻近单元将之也加入边界，然后在更新后的边界上查找最小的单元，然后重复上面的步骤，直到把所有的单元都变成边界单元。\n",
    "我们使用一个小根堆来存储边界上的所有单元的坐标及其最终水位高度。每次我们可以从堆中pop水位最低的单元，然后搜索并更新邻近单元的水位，然后将邻近单元push到堆中。\n",
    "那么什么时候可以结束呢？当堆为空时，那么可以肯定所有的单元的水位都被更新了。\n",
    "当然，一个边界单元有可能会被重复地搜索到，因此如果搜索到重复的边界单元时直接忽略掉，因此我们访问了一个单元后，还需要标记其已经被访问过。\n",
    "\"\"\"\n",
    "from typing import List, Tuple, Dict\n",
    "import heapq\n",
    "import copy\n",
    "class Solution:\n",
    "    def trapRainWater(self, heightMap: List[List[int]]) -> int:\n",
    "        M,N = len(heightMap), len(heightMap[0])\n",
    "        water: List[List[int]] = copy.deepcopy(heightMap) #从heightMap中clone一个新的list\n",
    "        visted: List[List[bool]] = [[False for j in range(N)] for i in range(M)] #标记i,j是否被访问过。\n",
    "        OPEN: List[Tupe[int, int, int]] = []\n",
    "        for i in range(M):\n",
    "            heapq.heappush(OPEN, (heightMap[i][0], i, 0))\n",
    "            heapq.heappush(OPEN, (heightMap[i][N-1], i, N-1))\n",
    "            visted[i][0] = True\n",
    "            visted[i][N-1] = True\n",
    "        for j in range(N):\n",
    "            heapq.heappush(OPEN, (heightMap[0][j], 0, j))\n",
    "            heapq.heappush(OPEN, (heightMap[M-1][j], M-1, j))\n",
    "            visted[0][j] = True\n",
    "            visted[M-1][j] = True\n",
    "        \n",
    "        while True:\n",
    "            if len(OPEN) == 0: break\n",
    "            h, i,j = heapq.heappop(OPEN)\n",
    "            for m,n in [(i-1,j),(i+1,j),(i,j-1),(i,j+1)]:\n",
    "                if m<0 or n<0 or m>=M or n>=N or visted[m][n]:\n",
    "                    continue\n",
    "                water[m][n] = max(h, heightMap[m][n])\n",
    "                heapq.heappush(OPEN, (water[m][n],m,n))\n",
    "                visted[m][n] = True\n",
    "        \n",
    "        ret: int = 0\n",
    "        for m in range(M):\n",
    "            for n in range(N):\n",
    "                ret += water[m][n] - heightMap[m][n]\n",
    "\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "我们使用一个小根堆来存储边界上的所有单元的坐标及其最终水位高度。每次我们可以从堆中pop水位最低的单元，然后搜索并更新邻近单元的水位，然后将邻近单元push到堆中。\n",
    "那么什么时候可以结束呢？当堆为空时，那么可以肯定所有的单元的水位都被更新了。\n",
    "当然，一个边界单元有可能会被重复地搜索到，因此如果搜索到重复的边界单元时直接忽略掉，因此我们访问了一个单元后，还需要标记其已经被访问过。\n",
    "\"\"\"\n",
    "from typing import List, Tuple, Dict\n",
    "import heapq\n",
    "import copy\n",
    "class Solution:\n",
    "    def trapRainWater(self, heightMap: List[List[int]]) -> int:\n",
    "        M,N = len(heightMap), len(heightMap[0])\n",
    "        water: List[List[int]] = copy.deepcopy(heightMap) #从heightMap中clone一个新的list\n",
    "        visted: List[List[bool]] = [[False for j in range(N)] for i in range(M)] #标记i,j是否被访问过。\n",
    "        OPEN: List[Tupe[int, int, int]] = []\n",
    "        for i in range(M):\n",
    "            heapq.heappush(OPEN, (heightMap[i][0], i, 0))\n",
    "            heapq.heappush(OPEN, (heightMap[i][N-1], i, N-1))\n",
    "            visted[i][0] = True\n",
    "            visted[i][N-1] = True\n",
    "        for j in range(N):\n",
    "            heapq.heappush(OPEN, (heightMap[0][j], 0, j))\n",
    "            heapq.heappush(OPEN, (heightMap[M-1][j], M-1, j))\n",
    "            visted[0][j] = True\n",
    "            visted[M-1][j] = True\n",
    "        \n",
    "        while True:\n",
    "            if len(OPEN) == 0: break\n",
    "            h, i,j = heapq.heappop(OPEN)\n",
    "            for m,n in [(i-1,j),(i+1,j),(i,j-1),(i,j+1)]:\n",
    "                if m<0 or n<0 or m>=M or n>=N or visted[m][n]:\n",
    "                    continue\n",
    "                water[m][n] = max(h, heightMap[m][n])\n",
    "                heapq.heappush(OPEN, (water[m][n],m,n))\n",
    "                visted[m][n] = True\n",
    "        \n",
    "        ret: int = 0\n",
    "        for m in range(M):\n",
    "            for n in range(N):\n",
    "                ret += water[m][n] - heightMap[m][n]\n",
    "\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trapRainWater(self, heightMap: List[List[int]]) -> int:\n",
    "        if not heightMap or len(heightMap)<=2 or len(heightMap[0])<=2:\n",
    "            return 0\n",
    "        m,n= len(heightMap),len(heightMap[0])\n",
    "        visited = [[False for _ in range(n)]for _ in range(m)]\n",
    "        water = [[0 for _ in range(n)]for _ in range(m)]\n",
    "        hp = []\n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i==0 or i==m-1 or j==0 or j==n-1:\n",
    "                    visited[i][j] = True\n",
    "                    heapq.heappush(hp,(heightMap[i][j],(i,j)))\n",
    "        dirs = [[1,0],[-1,0],[0,1],[0,-1]]\n",
    "        while hp:\n",
    "            height,pos = heapq.heappop(hp)\n",
    "            for d in dirs:\n",
    "                x,y = pos[0]+d[0],pos[1]+d[1]\n",
    "                if 0<=x<=m-1 and 0<=y<=n-1 and not visited[x][y]:\n",
    "                    water[x][y] = max(heightMap[x][y],height)\n",
    "                    res += water[x][y] -heightMap[x][y]\n",
    "                    visited[x][y] = True\n",
    "                    heapq.heappush(hp,(water[x][y],(x,y)))\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def trapRainWater(self, heightMap: List[List[int]]) -> int:\n",
    "        n = len(heightMap)\n",
    "        m = len(heightMap[0])\n",
    "        if n<=2 or m<=2:\n",
    "            return 0 \n",
    "\n",
    "        maxHeight = max(max(row) for row in heightMap)\n",
    "        water = [[maxHeight for _ in range(m)] for _ in range(n)]\n",
    "        direction = [(1,0),(0,1),(-1,0),(0,-1)]\n",
    "        # print(water)\n",
    "        queue = deque()\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if i==0 or i==n-1 or j==0 or j==m-1:\n",
    "                    if water[i][j] > heightMap[i][j]:\n",
    "                        water[i][j] = heightMap[i][j]\n",
    "                        queue.append((i,j))\n",
    "        print(queue)\n",
    "        while queue:   \n",
    "            x, y = queue.popleft()\n",
    "            for i,j in direction:\n",
    "                nx, ny = x+i,y+j\n",
    "                if nx<0 or nx>n-1 or ny<0 or ny>m-1:\n",
    "                    continue\n",
    "                if  water[x][y]< water[nx][ny] and water[nx][ny] >= heightMap[nx][ny]:\n",
    "                    water[nx][ny]=max(heightMap[nx][ny],water[x][y])\n",
    "                    queue.append((nx,ny))\n",
    "        print(water)\n",
    "        res = 0\n",
    "        \n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                res+= water[i][j]-heightMap[i][j] \n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trapRainWater(self, heightMap: List[List[int]]) -> int:\n",
    "        m, n = len(heightMap), len(heightMap[0])\n",
    "        steps = [(-1, 0), (1, 0), (0, -1), (0, 1)]\n",
    "        visited = [[False] * n for _ in range(m)]\n",
    "        height = [[-1] * n for _ in range(m)]\n",
    "\n",
    "        pq = []\n",
    "        for i, j in itertools.product(range(m), range(n)):\n",
    "            if i == 0 or i == m - 1 or j == 0 or j == n - 1:\n",
    "                visited[i][j] = True\n",
    "                height[i][j] = heightMap[i][j]\n",
    "                heapq.heappush(pq, (height[i][j], (i, j)))\n",
    "\n",
    "        s = 0\n",
    "        while len(pq) > 0:\n",
    "            h, (i, j) = heapq.heappop(pq)\n",
    "\n",
    "            for di, dj in steps:\n",
    "                ni, nj = i + di, j + dj\n",
    "                if 0 <= ni < m and 0 <= nj < n and not visited[ni][nj]:\n",
    "                    height[ni][nj] = max(heightMap[ni][nj], h)\n",
    "                    s += height[ni][nj] - heightMap[ni][nj]\n",
    "                    visited[ni][nj] = True\n",
    "                    heapq.heappush(pq, (height[ni][nj], (ni, nj)))\n",
    "\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trapRainWater(self, heightMap: List[List[int]]) -> int:\n",
    "        h = []\n",
    "        row = len(heightMap)\n",
    "        col = len(heightMap[0])\n",
    "        water = [[-1] * col for _ in range(row)]\n",
    "\n",
    "\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if i == 0 or i == row - 1 or j == 0 or j == col - 1:\n",
    "                    heapq.heappush(h, [heightMap[i][j], i, j])\n",
    "                    water[i][j] = heightMap[i][j]\n",
    "        \n",
    "        res = 0\n",
    "        while h:\n",
    "            height, x, y = heappop(h)\n",
    "            for dx, dy in [[0, 1], [1, 0], [0, -1], [-1, 0]]:\n",
    "                nx = x + dx\n",
    "                ny = y + dy\n",
    "                if nx < 0 or nx >= row or ny < 0 or ny >= col or water[nx][ny] > 0:\n",
    "                    continue\n",
    "                # water[nx][ny] = height\n",
    "                if height < heightMap[nx][ny]:\n",
    "                    water[nx][ny] = heightMap[nx][ny] \n",
    "                else:\n",
    "                    water[nx][ny] = height\n",
    "                    res += height - heightMap[nx][ny]\n",
    "                heapq.heappush(h, [water[nx][ny], nx, ny])\n",
    "\n",
    "        print(water)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def trapRainWater(self, heightMap: List[List[int]]) -> int:\n",
    "\n",
    "        heap_map = []\n",
    "        flag = [[0 for i in heightMap[0]] for i in heightMap]\n",
    "        cur_max, max_v = float(\"inf\"),0\n",
    "        direction = [[0,1], [1,0], [0,-1], [-1,0]]\n",
    "        cur_x, cur_y = 0, 0\n",
    "        r = len(heightMap)\n",
    "        c = len(heightMap[0])\n",
    "        for x,y in direction:\n",
    "            while 0<=cur_x<r and 0<=cur_y<c and 0<=cur_x+x<r and 0<=cur_y+y<c:\n",
    "                cur_max = min(cur_max, heightMap[cur_x][cur_y] )\n",
    "                heappush(heap_map, [heightMap[cur_x][cur_y], cur_x, cur_y ])\n",
    "                flag[cur_x][cur_y] = 1\n",
    "                cur_x, cur_y = cur_x+x, cur_y+y\n",
    "\n",
    "        while heap_map:\n",
    "            cur_v , cur_x, cur_y = heappop(heap_map)\n",
    "            cur_max = max(cur_max, cur_v)\n",
    "            for x,y in direction:\n",
    "                if 0<=cur_x+x<r and 0<=cur_y+y<c and flag[cur_x+x][cur_y+y]==0:\n",
    "                    flag[cur_x+x][cur_y+y]=1\n",
    "                    heappush(heap_map, [heightMap[cur_x+x][cur_y+y], cur_x+x, cur_y+y ])\n",
    "                    if heightMap[cur_x+x][cur_y+y]<cur_max:\n",
    "                        max_v += -heightMap[cur_x+x][cur_y+y] + cur_max\n",
    "        return max_v"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "我们使用一个小根堆来存储边界上的所有单元的坐标及其最终水位高度。每次我们可以从堆中pop水位最低的单元，然后搜索并更新邻近单元的水位，然后将邻近单元push到堆中。\n",
    "那么什么时候可以结束呢？当堆为空时，那么可以肯定所有的单元的水位都被更新了。\n",
    "当然，一个边界单元有可能会被重复地搜索到，因此如果搜索到重复的边界单元时直接忽略掉，因此我们访问了一个单元后，还需要标记其已经被访问过。\n",
    "\"\"\"\n",
    "from typing import List, Tuple, Dict\n",
    "import heapq\n",
    "import copy\n",
    "class Solution:\n",
    "    def trapRainWater(self, heightMap: List[List[int]]) -> int:\n",
    "        M,N = len(heightMap), len(heightMap[0])\n",
    "        water: List[List[int]] = copy.deepcopy(heightMap) #从heightMap中clone一个新的list\n",
    "        visted: List[List[bool]] = [[False for j in range(N)] for i in range(M)] #标记i,j是否被访问过。\n",
    "        OPEN: List[Tupe[int, int, int]] = []\n",
    "        for i in range(M):\n",
    "            heapq.heappush(OPEN, (heightMap[i][0], i, 0))\n",
    "            heapq.heappush(OPEN, (heightMap[i][N-1], i, N-1))\n",
    "            visted[i][0] = True\n",
    "            visted[i][N-1] = True\n",
    "        for j in range(N):\n",
    "            heapq.heappush(OPEN, (heightMap[0][j], 0, j))\n",
    "            heapq.heappush(OPEN, (heightMap[M-1][j], M-1, j))\n",
    "            visted[0][j] = True\n",
    "            visted[M-1][j] = True\n",
    "        \n",
    "        while True:\n",
    "            if len(OPEN) == 0: break\n",
    "            h, i,j = heapq.heappop(OPEN)\n",
    "            print(h,i,j)\n",
    "            for m,n in [(i-1,j),(i+1,j),(i,j-1),(i,j+1)]:\n",
    "                if m<0 or n<0 or m>=M or n>=N or visted[m][n]:\n",
    "                    continue\n",
    "                print('---',(m,n))\n",
    "                water[m][n] = max(h, heightMap[m][n])\n",
    "                heapq.heappush(OPEN, (water[m][n],m,n))\n",
    "                visted[m][n] = True\n",
    "        print(heightMap)\n",
    "        print(water)\n",
    "        \n",
    "        ret: int = 0\n",
    "        for m in range(M):\n",
    "            for n in range(N):\n",
    "                ret += water[m][n] - heightMap[m][n]\n",
    "\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class block:\n",
    "    def __init__(self,height,x,y):\n",
    "        self.height = height\n",
    "        self.x = x\n",
    "        self.y = y\n",
    "    def __lt__(self, other):\n",
    "        return self.height<other.height\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def trapRainWater(self, heightMap: List[List[int]]) -> int:\n",
    "        if len(heightMap) <= 2 or len(heightMap[0]) <= 2:\n",
    "            return 0\n",
    "\n",
    "        m = len(heightMap)\n",
    "        n = len(heightMap[0])\n",
    "        used = [[False] * n for _ in range(m)]\n",
    "\n",
    "        queue = []\n",
    "\n",
    "        # heapq.heappush(queue, (p, xxx))\n",
    "        # 可以向堆中以p为key插入(p,xxx)\n",
    "\n",
    "        for i in range(m):\n",
    "            used[i][0] = True\n",
    "            heapq.heappush(queue, block(heightMap[i][0], i, 0))\n",
    "            used[i][n - 1] = True\n",
    "            heapq.heappush(queue, block(heightMap[i][n-1], i, n-1))\n",
    "\n",
    "        for i in range(1, n - 1):\n",
    "            used[0][i] = True\n",
    "            heapq.heappush(queue, block(heightMap[0][i], 0, i))\n",
    "            used[m - 1][i] = True\n",
    "            heapq.heappush(queue, block(heightMap[m-1][i], m-1, i))\n",
    "\n",
    "        # 先布满边界，然后从边界“最小”点向“内”搜索并更新边界，直到搜索完全部节点\n",
    "\n",
    "        res = 0\n",
    "\n",
    "        while queue:\n",
    "            element = heapq.heappop(queue)\n",
    "            # 拿出最小点\n",
    "\n",
    "            minH = element.height\n",
    "            x = element.x\n",
    "            y = element.y\n",
    "            for (xx, yy) in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:\n",
    "                if 0 <= xx < m and 0 <= yy < n and used[xx][yy] == False:\n",
    "                    used[xx][yy] = True\n",
    "\n",
    "                    res += max(minH - heightMap[xx][yy], 0)\n",
    "                    # 能否存水\n",
    "\n",
    "                    heapq.heappush(queue, block(max(heightMap[xx][yy], minH), xx, yy))\n",
    "                    # 更新边界\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from queue import PriorityQueue\n",
    "from itertools import count\n",
    "class Solution:\n",
    "    def trapRainWater(self, heightMap: List[List[int]]) -> int:\n",
    "        if not heightMap or not heightMap[0] or len(heightMap) < 3 or len(heightMap[0]) < 3:\n",
    "            return 0\n",
    "\n",
    "        row = len(heightMap)\n",
    "        col = len(heightMap[0])\n",
    "        used_matrix = [[False for i in range(col)] for _ in range(row)]\n",
    "\n",
    "        index = count(0)\n",
    "        q = PriorityQueue()\n",
    "        for i in range(col):\n",
    "            self.fill_node(0, i, next(index), q, used_matrix, heightMap)\n",
    "        for i in range(1, row):\n",
    "            self.fill_node(i, col - 1, next(index), q, used_matrix, heightMap)\n",
    "        for i in range(col - 2, -1, -1):\n",
    "            self.fill_node(row- 1, i, next(index), q, used_matrix, heightMap)\n",
    "        for i in range(row - 2, 0, -1):\n",
    "            self.fill_node(i, 0, next(index), q, used_matrix, heightMap)\n",
    "\n",
    "        cnt = 0\n",
    "        max_height = 0\n",
    "\n",
    "        while not q.empty():\n",
    "            _, _, node = q.get()\n",
    "            max_height = max(max_height, node.val)\n",
    "\n",
    "            if max_height > node.val:\n",
    "                cnt += max_height - node.val\n",
    "\n",
    "            i, j = node.row, node.col\n",
    "            used_matrix[i][j] = True\n",
    "\n",
    "            if i + 1 < row and not used_matrix[i + 1][j]:\n",
    "                self.fill_node(i+1, j, next(index), q, used_matrix, heightMap)\n",
    "\n",
    "            if j + 1 < col and not used_matrix[i][j + 1]:\n",
    "                self.fill_node(i, j+1, next(index), q, used_matrix, heightMap)\n",
    "\n",
    "            if i - 1 >= 0 and not used_matrix[i - 1][j]:\n",
    "                self.fill_node(i-1, j, next(index), q, used_matrix, heightMap)\n",
    "\n",
    "            if j - 1 >= 0 and not used_matrix[i][j - 1]:\n",
    "                self.fill_node(i, j-1, next(index), q, used_matrix, heightMap)\n",
    "        return cnt\n",
    "    \n",
    "    def fill_node(self, i, j, index, q, used_matrix, matrix):\n",
    "        node = Node(matrix[i][j], i, j)\n",
    "        q.put((node.val, index, node))\n",
    "        used_matrix[i][j] = True\n",
    "        \n",
    "class Node(object):\n",
    "    def __init__(self, val, row, col):\n",
    "        self.val = val\n",
    "        self.row = row\n",
    "        self.col = col\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from queue import PriorityQueue\n",
    "from itertools import count\n",
    "class Solution:\n",
    "    def trapRainWater(self, heightMap: List[List[int]]) -> int:\n",
    "        if not heightMap or not heightMap[0] or len(heightMap) < 3 or len(heightMap[0]) < 3:\n",
    "            return 0\n",
    "\n",
    "        row = len(heightMap)\n",
    "        col = len(heightMap[0])\n",
    "        used_matrix = [[False for i in range(col)] for _ in range(row)]\n",
    "\n",
    "        index = count(0)\n",
    "        q = PriorityQueue()\n",
    "        for i in range(col):\n",
    "            self.fill_node(0, i, next(index), q, used_matrix, heightMap)\n",
    "        for i in range(1, row):\n",
    "            self.fill_node(i, col - 1, next(index), q, used_matrix, heightMap)\n",
    "        for i in range(col - 2, -1, -1):\n",
    "            self.fill_node(row- 1, i, next(index), q, used_matrix, heightMap)\n",
    "        for i in range(row - 2, 0, -1):\n",
    "            self.fill_node(i, 0, next(index), q, used_matrix, heightMap)\n",
    "\n",
    "        cnt = 0\n",
    "        max_height = 0\n",
    "\n",
    "        while not q.empty():\n",
    "            _, _, node = q.get()\n",
    "            max_height = max(max_height, node.val)\n",
    "\n",
    "            if max_height > node.val:\n",
    "                cnt += max_height - node.val\n",
    "\n",
    "            i, j = node.row, node.col\n",
    "            used_matrix[i][j] = True\n",
    "\n",
    "            if i + 1 < row and not used_matrix[i + 1][j]:\n",
    "                self.fill_node(i+1, j, next(index), q, used_matrix, heightMap)\n",
    "\n",
    "            if j + 1 < col and not used_matrix[i][j + 1]:\n",
    "                self.fill_node(i, j+1, next(index), q, used_matrix, heightMap)\n",
    "\n",
    "            if i - 1 >= 0 and not used_matrix[i - 1][j]:\n",
    "                self.fill_node(i-1, j, next(index), q, used_matrix, heightMap)\n",
    "\n",
    "            if j - 1 >= 0 and not used_matrix[i][j - 1]:\n",
    "                self.fill_node(i, j-1, next(index), q, used_matrix, heightMap)\n",
    "        return cnt\n",
    "    \n",
    "    def fill_node(self, i, j, index, q, used_matrix, matrix):\n",
    "        node = Node(matrix[i][j], i, j)\n",
    "        q.put((node.val, index, node))\n",
    "        used_matrix[i][j] = True\n",
    "        \n",
    "class Node(object):\n",
    "    def __init__(self, val, row, col):\n",
    "        self.val = val\n",
    "        self.row = row\n",
    "        self.col = col\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trapRainWater(self, heightMap: List[List[int]]) -> int:\n",
    "        m, n = len(heightMap), len(heightMap[0])\n",
    "        if m <= 2 or n <= 2:\n",
    "            return 0\n",
    "        res = 0\n",
    "        edge = []\n",
    "        visited = [[0 for _ in range(n)] for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i == 0 or i == m-1 or j == 0 or j == n-1:\n",
    "                    edge.append([heightMap[i][j], i, j])\n",
    "                    visited[i][j] = 1\n",
    "        edge = sorted(edge, key=lambda x:x[0], reverse=True)\n",
    "        while edge:\n",
    "            h, x, y = edge[-1]\n",
    "            del edge[-1]\n",
    "            flag = False\n",
    "            for (newx, newy) in ((x-1,y),(x+1,y),(x,y-1),(x,y+1)):\n",
    "                if 0 < newx < m-1 and 0 < newy < n-1 and visited[newx][newy] == 0:\n",
    "                    if heightMap[newx][newy] > h:\n",
    "                        flag = True\n",
    "                    elif heightMap[newx][newy] < h:\n",
    "                        res += h - heightMap[newx][newy]\n",
    "                        heightMap[newx][newy] = h\n",
    "                    edge.append([heightMap[newx][newy], newx, newy])\n",
    "                    visited[newx][newy] = 1\n",
    "            if flag == True:\n",
    "                edge = sorted(edge, key=lambda x:x[0], reverse=True)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Point:\n",
    "    def __init__(self, x, y, value):\n",
    "        self.x = x\n",
    "        self.y = y\n",
    "        self.value = value\n",
    "\n",
    "    def __lt__(self, other):\n",
    "        return self.value < other.value\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def trapRainWater(self, heightMap: List[List[int]]) -> int:\n",
    "        m = len(heightMap)\n",
    "        n = len(heightMap[0])\n",
    "        import heapq\n",
    "        pq = []\n",
    "        heapq.heapify(pq)\n",
    "        vis = [[False for _ in range(n)] for _ in range(m)]\n",
    "\n",
    "        def findNeighbor(x, y):\n",
    "            res = []\n",
    "            if x == -1 and y == -1:\n",
    "                for j in range(0, n):\n",
    "                    res.append((0, j))\n",
    "                    vis[0][j] = True\n",
    "                for j in range(0, n):\n",
    "                    res.append((m - 1, j))\n",
    "                    vis[m - 1][j] = True\n",
    "                for i in range(1, m - 1):\n",
    "                    res.append((i, 0))\n",
    "                    vis[i][0] = True\n",
    "                for i in range(1, m - 1):\n",
    "                    res.append((i, n - 1))\n",
    "                    vis[i][n - 1] = True\n",
    "            else:\n",
    "                offsets = [(0, 1), (0, -1), (1, 0), (-1, 0)]\n",
    "                for offset in offsets:\n",
    "                    x_ = x + offset[0]\n",
    "                    y_ = y + offset[1]\n",
    "                    if 0 <= x_ < m and 0 <= y_ < n and not vis[x_][y_]:\n",
    "                        res.append((x_, y_))\n",
    "                        vis[x_][y_] = True\n",
    "            return res\n",
    "\n",
    "        source = Point(-1, -1, 0)\n",
    "        heapq.heappush(pq, source)\n",
    "        cur_max = 0\n",
    "        ans = 0\n",
    "        while pq:\n",
    "            point = heapq.heappop(pq)\n",
    "            # print('pop', point.x, point.y, point.value)\n",
    "            x = point.x\n",
    "            y = point.y\n",
    "            if x != -1 and y != -1 and cur_max < heightMap[x][y]:\n",
    "                cur_max = heightMap[x][y]\n",
    "            neighbors = findNeighbor(x, y)\n",
    "            for neighbor in neighbors:\n",
    "                x_ = neighbor[0]\n",
    "                y_ = neighbor[1]\n",
    "                neighbor = Point(x_, y_, heightMap[x_][y_])\n",
    "                if heightMap[x_][y_] < cur_max:\n",
    "                    ans += cur_max - heightMap[x_][y_]\n",
    "                heapq.heappush(pq, neighbor)\n",
    "                # print('push', neighbor.x, neighbor.y, neighbor.value)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class block:\n",
    "    def __init__(self,height,x,y):\n",
    "        self.height = height\n",
    "        self.x = x\n",
    "        self.y = y\n",
    "    def __lt__(self, other):\n",
    "        return self.height<other.height\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def trapRainWater(self, heightMap: List[List[int]]) -> int:\n",
    "        if len(heightMap) <= 2 or len(heightMap[0]) <= 2:\n",
    "            return 0\n",
    "\n",
    "        m = len(heightMap)\n",
    "        n = len(heightMap[0])\n",
    "        used = [[False] * n for _ in range(m)]\n",
    "\n",
    "        queue = []\n",
    "\n",
    "        # heapq.heappush(queue, (p, xxx))\n",
    "        # 可以向堆中以p为key插入(p,xxx)\n",
    "\n",
    "        for i in range(m):\n",
    "            used[i][0] = True\n",
    "            heapq.heappush(queue, block(heightMap[i][0], i, 0))\n",
    "            used[i][n - 1] = True\n",
    "            heapq.heappush(queue, block(heightMap[i][n-1], i, n-1))\n",
    "\n",
    "        for i in range(1, n - 1):\n",
    "            used[0][i] = True\n",
    "            heapq.heappush(queue, block(heightMap[0][i], 0, i))\n",
    "            used[m - 1][i] = True\n",
    "            heapq.heappush(queue, block(heightMap[m-1][i], m-1, i))\n",
    "\n",
    "        # 先布满边界，然后从边界“最小”点向“内”搜索并更新边界，直到搜索完全部节点\n",
    "\n",
    "        res = 0\n",
    "\n",
    "        while queue:\n",
    "            element = heapq.heappop(queue)\n",
    "            # 拿出最小点\n",
    "\n",
    "            minH = element.height\n",
    "            x = element.x\n",
    "            y = element.y\n",
    "            for (xx, yy) in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:\n",
    "                if 0 <= xx < m and 0 <= yy < n and used[xx][yy] == False:\n",
    "                    used[xx][yy] = True\n",
    "\n",
    "                    res += max(minH - heightMap[xx][yy], 0)\n",
    "                    # 能否存水\n",
    "\n",
    "                    heapq.heappush(queue, block(max(heightMap[xx][yy], minH), xx, yy))\n",
    "                    # 更新边界\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import heappop, heappush \n",
    "\n",
    "class Solution:\n",
    "    def trapRainWater(self, heightMap: List[List[int]]) -> int:\n",
    "        m, n = len(heightMap), len(heightMap[0])\n",
    "        pq, visited = [], set()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i==0 or i==m-1 or j==0 or j==n-1:\n",
    "                    heappush(pq, (heightMap[i][j], i*n+j))\n",
    "                    visited.add(i*n+j)\n",
    "\n",
    "        ans = 0\n",
    "        while pq:\n",
    "            height, pos = heappop(pq)\n",
    "            x, y = pos//n, pos%n\n",
    "            for newx, newy in [[x+1, y], [x-1, y], [x, y+1], [x, y-1]]:\n",
    "                newpos = newx*n+newy\n",
    "                if 0 <= newx < m and 0 <= newy < n and newpos not in visited:\n",
    "                    visited.add(newpos)\n",
    "                    if height > heightMap[newx][newy]:\n",
    "                        ans += height - heightMap[newx][newy]\n",
    "                    heappush(pq, (max(height, heightMap[newx][newy]), newpos))\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trapRainWater(self, heightMap: List[List[int]]) -> int:\n",
    "        # Prim算法解决3D接雨水\n",
    "        visited = set()\n",
    "        import heapq\n",
    "        queue = []\n",
    "        m = len(heightMap)\n",
    "        n = len(heightMap[0])\n",
    "        # 边缘不会接雨水\n",
    "        for i in range(m):\n",
    "            heapq.heappush(queue, (heightMap[i][0], i, 0))\n",
    "            heapq.heappush(queue, (heightMap[i][n-1], i, n-1))\n",
    "            visited.add(i*n)\n",
    "            visited.add(i*n+n-1)\n",
    "        for i in range(1, n):\n",
    "            heapq.heappush(queue, (heightMap[0][i], 0, i))\n",
    "            heapq.heappush(queue, (heightMap[m-1][i], m-1, i))\n",
    "            visited.add(i)\n",
    "            visited.add((m-1)*n+i)\n",
    "        # prime算法，每次选择权值最小的边，在这里就是选择最矮的柱子\n",
    "        d = [(0, 1), (0, -1), (-1, 0), (1, 0)]\n",
    "        res = 0\n",
    "        while queue:\n",
    "            if len(visited) == m*n:\n",
    "                return res\n",
    "            h, x, y = heapq.heappop(queue)\n",
    "            for i in range(4):\n",
    "                nx = x+d[i][0]\n",
    "                ny = y+d[i][1]\n",
    "                if 0<=nx<m and 0<=ny<n and nx*n+ny not in visited:\n",
    "                    visited.add(nx*n+ny)\n",
    "                    if heightMap[nx][ny] < h:  # 注意，h不能写成heightMap[x][y]\n",
    "                        res += h - heightMap[nx][ny]  # 注意，h不能写成heightMap[x][y]\n",
    "                    # 注意，入队列的柱子高度是max(heightMap[nx][ny], heightMap[x][y])，因为这代表(nx,ny)坐标d[i]方向的最高点，与一维接雨水的单调栈差不多\n",
    "                    heapq.heappush(queue, (max(heightMap[nx][ny], h), nx, ny))   # 注意，h不能写成heightMap[x][y]\n",
    "        if len(visited) == m*n:\n",
    "            return res\n",
    "        else:\n",
    "            return 0\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trapRainWater(self, heightMap: List[List[int]]) -> int:\n",
    "        # Prim算法解决3D接雨水\n",
    "        visited = set()\n",
    "        import heapq\n",
    "        queue = []\n",
    "        m = len(heightMap)\n",
    "        n = len(heightMap[0])\n",
    "        # 边缘不会接雨水\n",
    "        for i in range(m):\n",
    "            heapq.heappush(queue, (heightMap[i][0], i, 0))\n",
    "            heapq.heappush(queue, (heightMap[i][n-1], i, n-1))\n",
    "            visited.add(i*n)\n",
    "            visited.add(i*n+n-1)\n",
    "        for i in range(1, n):\n",
    "            heapq.heappush(queue, (heightMap[0][i], 0, i))\n",
    "            heapq.heappush(queue, (heightMap[m-1][i], m-1, i))\n",
    "            visited.add(i)\n",
    "            visited.add((m-1)*n+i)\n",
    "        # prime算法，每次选择权值最小的边，在这里就是选择最矮的柱子\n",
    "        d = [(0, 1), (0, -1), (-1, 0), (1, 0)]\n",
    "        res = 0\n",
    "        while queue:\n",
    "            if len(visited) == m*n:\n",
    "                return res\n",
    "            h, x, y = heapq.heappop(queue)\n",
    "            for i in range(4):\n",
    "                nx = x+d[i][0]\n",
    "                ny = y+d[i][1]\n",
    "                if 0<=nx<m and 0<=ny<n and nx*n+ny not in visited:\n",
    "                    visited.add(nx*n+ny)\n",
    "                    if heightMap[nx][ny] < h:  # 注意，h不能写成heightMap[x][y]\n",
    "                        res += h - heightMap[nx][ny]  # 注意，h不能写成heightMap[x][y]\n",
    "                    # 注意，入队列的柱子高度是max(heightMap[nx][ny], heightMap[x][y])，因为这代表(nx,ny)坐标d[i]方向的最高点，与一维接雨水的单调栈差不多\n",
    "                    heapq.heappush(queue, (max(heightMap[nx][ny], h), nx, ny))   # 注意，h不能写成heightMap[x][y]\n",
    "        if len(visited) == m*n:\n",
    "            return res\n",
    "        else:\n",
    "            return 0\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trapRainWater(self, heightMap: List[List[int]]) -> int:\n",
    "        if len(heightMap) <= 2 or len(heightMap[0]) <= 2:\n",
    "            return 0\n",
    "\n",
    "        m, n = len(heightMap), len(heightMap[0])\n",
    "        visited = set()\n",
    "        pq = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i == 0 or i == m - 1 or j == 0 or j == n - 1:\n",
    "                    visited.add(i * n + j)\n",
    "                    heapq.heappush(pq, (heightMap[i][j], i * n + j))\n",
    "        \n",
    "        res = 0\n",
    "        dirs = [-1, 0, 1, 0, -1]\n",
    "        while pq:\n",
    "            height, position = heapq.heappop(pq)\n",
    "            for k in range(4):\n",
    "                nx, ny = position // n + dirs[k], position % n + dirs[k + 1]\n",
    "                if nx >= 0 and nx < m and ny >= 0 and ny < n and nx * n + ny not in visited:\n",
    "                    if height > heightMap[nx][ny]:\n",
    "                        res += height - heightMap[nx][ny]\n",
    "                    visited.add(nx * n + ny)\n",
    "                    heapq.heappush(pq, (max(height, heightMap[nx][ny]), nx * n + ny))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.row = 0\n",
    "        self.col = 0\n",
    "        self.HM = None\n",
    "        self.FRZ = None #self.FRZ[i][j]==True表示这个点高度已经固定\n",
    "        self.ret = 0\n",
    "\n",
    "    def fill(self,i,j):\n",
    "        '''向ij区域灌水,返回是否能容纳一格水'''\n",
    "        if self.FRZ[i][j]:\n",
    "            return False \n",
    "\n",
    "        #print(\"fill\",i,j)\n",
    "        \n",
    "        hh = self.HM[i][j]  #染色高度为h的连通域\n",
    "        self.HM[i][j] = self.HM[i][j]*(-1)-1 #标记成小于0的\n",
    "        visited = []\n",
    "        cur = [(i,j)]\n",
    "        minH = float('inf') #围墙高度\n",
    "        while len(cur)!=0:\n",
    "            #print(cur)\n",
    "            #print(self.HM)\n",
    "            ncur = []\n",
    "            for c in cur:\n",
    "                visited.append(c)\n",
    "                if c[0]-1>=0: \n",
    "                    if self.HM[c[0]-1][c[1]]>=0: #未访问过\n",
    "                        if self.HM[c[0]-1][c[1]]==hh:\n",
    "                            ncur.append((c[0]-1,c[1]))\n",
    "                            self.HM[c[0]-1][c[1]] = self.HM[c[0]-1][c[1]]*(-1)-1\n",
    "                        elif self.HM[c[0]-1][c[1]]>hh:\n",
    "                            minH = min(minH,self.HM[c[0]-1][c[1]]-hh)\n",
    "                        else:\n",
    "                            while self.fill(c[0]-1,c[1]) and self.HM[c[0]-1][c[1]]<hh:\n",
    "                                pass\n",
    "                            if self.HM[c[0]-1][c[1]]==hh:\n",
    "                                ncur.append((c[0]-1,c[1]))\n",
    "                                self.HM[c[0]-1][c[1]] = self.HM[c[0]-1][c[1]]*(-1)-1\n",
    "                            else: # 小于\n",
    "                                minH = 0\n",
    "                    else:\n",
    "                        realH = self.HM[c[0]-1][c[1]]*(-1)-1\n",
    "                        if realH==hh:\n",
    "                            pass\n",
    "                        elif realH>hh:\n",
    "                            minH = min(minH,realH-hh)\n",
    "                        else:\n",
    "                            print(\"error!\")\n",
    "                else:\n",
    "                    minH = 0\n",
    "\n",
    "                if c[0]+1<self.row: \n",
    "                    if self.HM[c[0]+1][c[1]]>=0: #未访问过\n",
    "                        if self.HM[c[0]+1][c[1]]==hh:\n",
    "                            ncur.append((c[0]+1,c[1]))\n",
    "                            self.HM[c[0]+1][c[1]] = self.HM[c[0]+1][c[1]]*(-1)-1\n",
    "                        elif self.HM[c[0]+1][c[1]]>hh:\n",
    "                            minH = min(minH,self.HM[c[0]+1][c[1]]-hh)\n",
    "                        else:\n",
    "                            while self.fill(c[0]+1,c[1]) and self.HM[c[0]+1][c[1]]<hh:\n",
    "                                pass\n",
    "                            if self.HM[c[0]+1][c[1]]==hh:\n",
    "                                ncur.append((c[0]+1,c[1]))\n",
    "                                self.HM[c[0]+1][c[1]] = self.HM[c[0]+1][c[1]]*(-1)-1\n",
    "                            else: # 小于\n",
    "                                minH = 0\n",
    "                    else:\n",
    "                        realH = self.HM[c[0]+1][c[1]]*(-1)-1\n",
    "                        if realH==hh:\n",
    "                            pass\n",
    "                        elif realH>hh:\n",
    "                            minH = min(minH,realH-hh)\n",
    "                        else:\n",
    "                            print(\"error!\")\n",
    "                else:\n",
    "                    minH = 0\n",
    "\n",
    "                if c[1]-1>=0: \n",
    "                    if self.HM[c[0]][c[1]-1]>=0: #未访问过\n",
    "                        if self.HM[c[0]][c[1]-1]==hh:\n",
    "                            ncur.append((c[0],c[1]-1))\n",
    "                            self.HM[c[0]][c[1]-1] = self.HM[c[0]][c[1]-1]*(-1)-1\n",
    "                        elif self.HM[c[0]][c[1]-1]>hh:\n",
    "                            minH = min(minH,self.HM[c[0]][c[1]-1]-hh)\n",
    "                        else:\n",
    "                            while self.fill(c[0],c[1]-1) and self.HM[c[0]][c[1]-1]<hh:\n",
    "                                pass\n",
    "                            if self.HM[c[0]][c[1]-1]==hh:\n",
    "                                ncur.append((c[0],c[1]-1))\n",
    "                                self.HM[c[0]][c[1]-1] = self.HM[c[0]][c[1]-1]*(-1)-1\n",
    "                            else: # 小于\n",
    "                                minH = 0\n",
    "                    else:\n",
    "                        realH = self.HM[c[0]][c[1]-1]*(-1)-1\n",
    "                        if realH==hh:\n",
    "                            pass\n",
    "                        elif realH>hh:\n",
    "                            minH = min(minH,realH-hh)\n",
    "                        else:\n",
    "                            print(\"error!\")\n",
    "                else:\n",
    "                    minH = 0\n",
    "\n",
    "                if c[1]+1<self.col: \n",
    "                    if self.HM[c[0]][c[1]+1]>=0: #未访问过\n",
    "                        if self.HM[c[0]][c[1]+1]==hh:\n",
    "                            ncur.append((c[0],c[1]+1))\n",
    "                            self.HM[c[0]][c[1]+1] = self.HM[c[0]][c[1]+1]*(-1)-1\n",
    "                        elif self.HM[c[0]][c[1]+1]>hh:\n",
    "                            minH = min(minH,self.HM[c[0]][c[1]+1]-hh)\n",
    "                        else:\n",
    "                            while self.fill(c[0],c[1]+1) and self.HM[c[0]][c[1]+1]<hh:\n",
    "                                pass\n",
    "                            if self.HM[c[0]][c[1]+1]==hh:\n",
    "                                ncur.append((c[0],c[1]+1))\n",
    "                                self.HM[c[0]][c[1]+1] = self.HM[c[0]][c[1]+1]*(-1)-1\n",
    "                            else: # 小于\n",
    "                                minH = 0\n",
    "                    else:\n",
    "                        realH = self.HM[c[0]][c[1]+1]*(-1)-1\n",
    "                        if realH==hh:\n",
    "                            pass\n",
    "                        elif realH>hh:\n",
    "                            minH = min(minH,realH-hh)\n",
    "                        else:\n",
    "                            print(\"error!\")\n",
    "                else:\n",
    "                    minH = 0\n",
    "            cur = ncur\n",
    "\n",
    "        if minH==0:\n",
    "            #装不下水\n",
    "            for v in visited:\n",
    "                self.HM[v[0]][v[1]] = self.HM[v[0]][v[1]]*(-1)-1  #解锁染色\n",
    "                self.FRZ[v[0]][v[1]] = True #高度固定\n",
    "            return False\n",
    "        else:\n",
    "            self.ret += minH*(len(visited))\n",
    "            #print(\"xxxx\",i,j,minH,len(visited))\n",
    "            for v in visited:\n",
    "                self.HM[v[0]][v[1]] = self.HM[v[0]][v[1]]*(-1)-1 + minH #解锁染色 + 注水\n",
    "            return True\n",
    "        \n",
    "\n",
    "\n",
    "    def trapRainWater(self, heightMap: List[List[int]]) -> int:\n",
    "        self.row = len(heightMap)\n",
    "        self.col = len(heightMap[0])\n",
    "        self.HM = heightMap\n",
    "        self.FRZ = []\n",
    "        for i in range(self.row):\n",
    "            self.FRZ.append([False]*self.col)\n",
    "\n",
    "        for i in range(self.row):\n",
    "            for j in range(self.col):\n",
    "                #print(i,j)\n",
    "                #print(self.HM)\n",
    "                #print(self.FRZ)\n",
    "                while self.fill(i,j):\n",
    "                    pass\n",
    "        \n",
    "        return self.ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trapRainWater(self, heightMap: List[List[int]]) -> int:\n",
    "        if len(heightMap) <= 2 or len(heightMap[0]) <= 2:\n",
    "            return 0\n",
    "\n",
    "        m, n = len(heightMap), len(heightMap[0])\n",
    "        seen = {}\n",
    "        pq = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i == 0 or i == m - 1 or j == 0 or j == n - 1:\n",
    "                    seen[(i, j)] = 1\n",
    "                    heapq.heappush(pq, (heightMap[i][j], i, j))\n",
    "        \n",
    "        res = 0\n",
    "        dirs = [-1, 0, 1, 0, -1]\n",
    "        while pq:\n",
    "            height, x, y = heapq.heappop(pq)\n",
    "            for k in range(4):\n",
    "                nx, ny = x + dirs[k], y + dirs[k + 1]\n",
    "                if nx >= 0 and nx < m and ny >= 0 and ny < n and (nx, ny) not in seen:\n",
    "                    if height > heightMap[nx][ny]:\n",
    "                        res += height - heightMap[nx][ny]\n",
    "                    seen[(nx, ny)] = 1\n",
    "                    heapq.heappush(pq, (max(height, heightMap[nx][ny]), nx, ny))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trapRainWater(self, heightMap: List[List[int]]) -> int:\n",
    "        #只有一层城墙的时候，不能接雨水\n",
    "        if len(heightMap)<=2 or len(heightMap[0])<=2:return 0\n",
    "\n",
    "        res=0\n",
    "        m,n=len(heightMap),len(heightMap[0])\n",
    "        visited=set()\n",
    "        heap=[]\n",
    "\n",
    "        #将最外圈的城墙放进小根堆中，首先pop出来的一定是最外圈城墙的最短板\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i==0 or i==m-1 or j==0 or j==n-1:\n",
    "                    visited.add((i,j))\n",
    "                    heapq.heappush(heap,(heightMap[i][j],i*n+j))\n",
    "        \n",
    "        #\n",
    "        dir=[-1,0,1,0,-1]\n",
    "        while heap:\n",
    "            height,path=heapq.heappop(heap)\n",
    "            for k in range(4):\n",
    "                x,y=path//n+dir[k],path%n+dir[k+1]\n",
    "                if 0<=x<m and 0<=y<n and (x,y) not in visited:\n",
    "                    if heightMap[x][y]<height:\n",
    "                        res+=height-heightMap[x][y]\n",
    "                    visited.add((x,y))\n",
    "                    heapq.heappush(heap,(max(heightMap[x][y],height),x*n+y))\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trapRainWater(self, heightMap: List[List[int]]) -> int:\n",
    "        m, n = len(heightMap), len(heightMap[0])\n",
    "\n",
    "        heap = []\n",
    "        visited = set()\n",
    "\n",
    "        for j in range(n):\n",
    "            heapq.heappush(heap, [heightMap[0][j], (0, j)])\n",
    "            heapq.heappush(heap, [heightMap[m-1][j], (m-1, j)])\n",
    "            visited.add(j)\n",
    "            visited.add((m-1) * n + j)\n",
    "        \n",
    "        for i in range(m):\n",
    "            heapq.heappush(heap, [heightMap[i][0], (i, 0)])\n",
    "            heapq.heappush(heap, [heightMap[i][n-1], (i, n-1)])\n",
    "            visited.add(i * n)\n",
    "            visited.add(i * n + n - 1)\n",
    "            \n",
    "        ans = 0\n",
    "        \n",
    "        while heap:\n",
    "            height, (x, y) = heapq.heappop(heap)\n",
    "\n",
    "            for diff_x, diff_y in [(-1, 0), (1, 0), (0, 1), (0, -1)]:\n",
    "                new_x, new_y = diff_x + x, diff_y + y\n",
    "                idx = new_x * n + new_y\n",
    "                if 0 <= new_x < m and 0 <= new_y < n and idx not in visited:\n",
    "                    if heightMap[new_x][new_y] < height:\n",
    "                        ans += height - heightMap[new_x][new_y]\n",
    "                    visited.add(idx)\n",
    "                    heapq.heappush(heap, [max(height, heightMap[new_x][new_y]), (new_x, new_y)])\n",
    "        \n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def trapRainWater(self, heightMap: List[List[int]]) -> int:\n",
    "        \"\"\"\n",
    "        水从高处往低处流，某个位置储水量取决于四周最低高度，从最外层向里层包抄，用小顶堆动态找到未访问位置最小的高度\n",
    "        \"\"\"\n",
    "\n",
    "        if not heightMap: return 0\n",
    "\n",
    "        ans = 0\n",
    "        heap = []\n",
    "        visited = set()\n",
    "        row = len(heightMap)\n",
    "        col = len(heightMap[0])\n",
    "\n",
    "        # 将最外层放入小顶堆\n",
    "        # 第一行和最后一行\n",
    "        for j in range(col):\n",
    "            # 将该位置的高度、横纵坐标插入堆\n",
    "            heapq.heappush(heap, [heightMap[0][j], 0, j])\n",
    "            heapq.heappush(heap, [heightMap[row - 1][j], row - 1, j])\n",
    "            visited.add((0, j))\n",
    "            visited.add((row - 1, j))\n",
    "\n",
    "        # 第一列和最后一列\n",
    "        for i in range(1, row - 1):\n",
    "            heapq.heappush(heap, [heightMap[i][0], i, 0])\n",
    "            heapq.heappush(heap, [heightMap[i][col - 1], i, col - 1])\n",
    "            visited.add((i, 0))\n",
    "            visited.add((i, col - 1))\n",
    "\n",
    "        while heap:\n",
    "            h, i, j = heapq.heappop(heap)\n",
    "            # 之前最低高度的四周已经探索过了，所以要更新为次低高度开始探索\n",
    "            # 从堆顶元素出发，探索四周储水位置\n",
    "            for x, y in [[0, 1], [1, 0], [0, -1], [-1, 0]]:\n",
    "                tmp_x = x + i\n",
    "                tmp_y = y + j\n",
    "                # 是否到达边界\n",
    "                if tmp_x < 0 or tmp_y < 0 or tmp_x >= row or tmp_y >= col or (tmp_x, tmp_y) in visited:\n",
    "                    continue\n",
    "\n",
    "                if heightMap[tmp_x][tmp_y] < h:\n",
    "                    ans += h - heightMap[tmp_x][tmp_y]\n",
    "\n",
    "                visited.add((tmp_x, tmp_y))\n",
    "\n",
    "                # 更新一下下高度\n",
    "                heapq.heappush(heap, [max(h, heightMap[tmp_x][tmp_y]), tmp_x, tmp_y])\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Directions:\n",
    "    dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]\n",
    "    diagonal_dirs = [(1, 1), (1, -1), (-1, 1), (-1, -1)]\n",
    "    all_dirs = dirs + diagonal_dirs\n",
    "\n",
    "class Solution:\n",
    "    def trapRainWater(self, heightMap: List[List[int]]) -> int:\n",
    "        m, n = len(heightMap), len(heightMap[0])\n",
    "        h = []\n",
    "        import heapq\n",
    "        dist = {}\n",
    "        for i in range(m):\n",
    "            heapq.heappush(h, (heightMap[i][0], i, 0))\n",
    "            heapq.heappush(h, (heightMap[i][n - 1], i, n - 1))\n",
    "        for j in range(1, n - 1):\n",
    "            heapq.heappush(h, (heightMap[0][j], 0, j))\n",
    "            heapq.heappush(h, (heightMap[m - 1][j], m - 1, j))\n",
    "        ans = 0\n",
    "        while h:\n",
    "            ph, x, y = heapq.heappop(h)\n",
    "            if (x, y) in dist: continue\n",
    "            dist[(x, y)] = max(heightMap[x][y], ph)\n",
    "            if ph > heightMap[x][y]:\n",
    "                ans += ph - heightMap[x][y]\n",
    "            for dx, dy in Directions.dirs:\n",
    "                nx, ny = x + dx, y + dy\n",
    "                if 0 <= nx < m and 0 <= ny < n and (nx, ny) not in dist:\n",
    "                    heapq.heappush(h, (dist[(x, y)], nx, ny))\n",
    "        # print(dist)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def trapRainWater(self, heightMap) -> int:\n",
    "        if len(heightMap) == 0:\n",
    "            return 0\n",
    "        if len(heightMap[0]) == 0:\n",
    "            return 0\n",
    "        count = 0\n",
    "        pq = []\n",
    "        visit = dict()\n",
    "        for i in range(len(heightMap)):\n",
    "            for j in range(len(heightMap[0])):\n",
    "                visit[(i,j)] = 0\n",
    "        for j in range(len(heightMap[0])):\n",
    "            heapq.heappush(pq,(heightMap[0][j],(0,j)))\n",
    "            heapq.heappush(pq,(heightMap[len(heightMap)-1][j],(len(heightMap)-1,j)))\n",
    "            visit[(0,j)] = 1\n",
    "            visit[(len(heightMap)-1,j)]=1\n",
    "        for i in range(1, len(heightMap)-1):\n",
    "            heapq.heappush(pq,(heightMap[i][0],(i,0)))\n",
    "            heapq.heappush(pq,(heightMap[i][len(heightMap[0])-1],(i,len(heightMap[0])-1)))\n",
    "            visit[(i,0)] = 1\n",
    "            visit[(i, len(heightMap[0])-1)] = 1\n",
    "\n",
    "        while len(pq) > 0:\n",
    "            h, (cur_i, cur_j) = heapq.heappop(pq)\n",
    "            for dir in [(1,0),(-1,0),(0,1),(0,-1)]:\n",
    "                n_i = cur_i + dir[0]\n",
    "                n_j = cur_j + dir[1]\n",
    "                if n_i > 0 and n_i < len(heightMap)-1 and n_j > 0 and n_j < len(heightMap[0]) - 1:\n",
    "                    if visit[(n_i,n_j)] == 0:\n",
    "                        if h > heightMap[n_i][n_j]:\n",
    "                            count += h-heightMap[n_i][n_j]\n",
    "                        visit[(n_i,n_j)] = 1\n",
    "                        heapq.heappush(pq, (max(h, heightMap[n_i][n_j]),(n_i,n_j)))\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Unit:\n",
    "    def __init__(self,height,index):\n",
    "        self.height = height\n",
    "        self.index = index\n",
    "    def __lt__(self,other):\n",
    "        return self.height < other.height\n",
    "class Solution:    \n",
    "    def trapRainWater(self, heightMap: List[List[int]]) -> int:\n",
    "\n",
    "        import heapq\n",
    "        m = len(heightMap)\n",
    "        n = len(heightMap[0])\n",
    "        ans = 0\n",
    "        visited = [[0]*n for _ in range(m)]\n",
    "        heap=[]\n",
    "        for i in range(n):    \n",
    "            heapq.heappush(heap,Unit(heightMap[0][i],(0,i)))\n",
    "            visited[0][i] = 1\n",
    "            heapq.heappush(heap,Unit(heightMap[m-1][i],(m-1,i)))\n",
    "            visited[m-1][i] = 1\n",
    "        for i in range(m):\n",
    "            heapq.heappush(heap,Unit(heightMap[i][0],(i,0)))\n",
    "            visited[i][0] = 1\n",
    "            heapq.heappush(heap,Unit(heightMap[i][n-1],(i,n-1)))\n",
    "            visited[i][n-1] = 1\n",
    "        min_height = heap[0].height\n",
    "        while heap:\n",
    "            unit = heapq.heappop(heap)\n",
    "            arroud = 200001\n",
    "            for index in [(unit.index[0]+1,unit.index[1]),(unit.index[0]-1,unit.index[1]),(unit.index[0],unit.index[1]+1),(unit.index[0],unit.index[1]-1)]:\n",
    "                if index[0] < 0 or index[0] >=m or index[1]<0 or index[1]>=n:\n",
    "                    continue\n",
    "                if visited[index[0]][index[1]]:\n",
    "                    continue\n",
    "                ans += max(0, -heightMap[index[0]][index[1]]+min_height)\n",
    "                arroud = min(heightMap[index[0]][index[1]],arroud)\n",
    "                heapq.heappush(heap, Unit(max(heightMap[index[0]][index[1]],min_height),index))\n",
    "                visited[index[0]][index[1]] = 1\n",
    "            if heap:\n",
    "                min_height = heap[0].height\n",
    "        return ans\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    directions = [\n",
    "        (1, 0),\n",
    "        (-1, 0),\n",
    "        (0, 1),\n",
    "        (0, -1),\n",
    "    ]\n",
    "\n",
    "    def trapRainWater(self, heightMap) -> int:\n",
    "        # 我们设每条路径的距离为该路径上所有点的高度的最大值。\n",
    "        # 假设有个超级源点，该源点到边界上每个点的距离，为边界上每个点的高度。\n",
    "        # 超级源点到矩形内各点的距离，是个最短路问题。可以使用任何一种最短路算法求解。这里使用 spfa 算法求解。\n",
    "\n",
    "        n, m = len(heightMap), len(heightMap[0])\n",
    "        dist, h, st = collections.defaultdict(lambda :float(\"inf\")), collections.deque(), set()\n",
    "\n",
    "        # 遍历边界\n",
    "        for i in range(n):\n",
    "            dist[(i, 0)] = heightMap[i][0]\n",
    "            if (i, 0) not in st:\n",
    "                h.append((i, 0))\n",
    "                st.add((i, 0))\n",
    "\n",
    "            dist[(i, m - 1)] = heightMap[i][m - 1]\n",
    "            if (i, m - 1) not in st:\n",
    "                h.append((i, m - 1))\n",
    "                st.add((i, m - 1))\n",
    "\n",
    "        for j in range(m):\n",
    "            dist[(0, j)] = heightMap[0][j]\n",
    "            if (0, j) not in st:\n",
    "                h.append((0, j))\n",
    "                st.add((0, j))\n",
    "\n",
    "            dist[(n - 1, j)] = heightMap[n - 1][j]\n",
    "            if (n - 1, j) not in st:\n",
    "                h.append((n - 1, j))\n",
    "                st.add((n - 1, j))\n",
    "\n",
    "        # spfa 求最短路\n",
    "        while h:\n",
    "            u = h.popleft()\n",
    "            st.remove(u)\n",
    "\n",
    "            for d in self.directions:\n",
    "                v = (u[0] + d[0], u[1] + d[1])\n",
    "                if v[0] < 0 or v[0] >= n or v[1] < 0 or v[1] >= m:\n",
    "                    continue\n",
    "\n",
    "                if dist[v] > max(dist[u], heightMap[v[0]][v[1]]):\n",
    "                    dist[v] = max(dist[u], heightMap[v[0]][v[1]])\n",
    "                    if v not in st:\n",
    "                        h.append(v)\n",
    "                        st.add(v)\n",
    "\n",
    "        # 求出最短路后，就可以求出最多能接多少水。\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                ans += dist[(i, j)] - heightMap[i][j]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Unit:\n",
    "    def __init__(self,height,index):\n",
    "        self.height = height\n",
    "        self.index = index\n",
    "    def __lt__(self,other):\n",
    "        return self.height < other.height\n",
    "class Solution:    \n",
    "    def trapRainWater(self, heightMap: List[List[int]]) -> int:\n",
    "\n",
    "        import heapq\n",
    "        m = len(heightMap)\n",
    "        n = len(heightMap[0])\n",
    "        ans = 0\n",
    "        visited = [[0]*n for _ in range(m)]\n",
    "        heap=[]\n",
    "        for i in range(n):    \n",
    "            heapq.heappush(heap,Unit(heightMap[0][i],(0,i)))\n",
    "            visited[0][i] = 1\n",
    "            heapq.heappush(heap,Unit(heightMap[m-1][i],(m-1,i)))\n",
    "            visited[m-1][i] = 1\n",
    "        for i in range(m):\n",
    "            heapq.heappush(heap,Unit(heightMap[i][0],(i,0)))\n",
    "            visited[i][0] = 1\n",
    "            heapq.heappush(heap,Unit(heightMap[i][n-1],(i,n-1)))\n",
    "            visited[i][n-1] = 1\n",
    "        min_height = heap[0].height\n",
    "        while heap:\n",
    "            unit = heapq.heappop(heap)\n",
    "            for index in [(unit.index[0]+1,unit.index[1]),(unit.index[0]-1,unit.index[1]),(unit.index[0],unit.index[1]+1),(unit.index[0],unit.index[1]-1)]:\n",
    "                if index[0] < 0 or index[0] >=m or index[1]<0 or index[1]>=n:\n",
    "                    continue\n",
    "                if visited[index[0]][index[1]]:\n",
    "                    continue\n",
    "                ans += max(0, -heightMap[index[0]][index[1]]+min_height)\n",
    "                heapq.heappush(heap, Unit(max(heightMap[index[0]][index[1]],min_height),index))\n",
    "                visited[index[0]][index[1]] = 1\n",
    "            if heap:\n",
    "                min_height = heap[0].height\n",
    "        return ans\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trapRainWater(self, heightMap: List[List[int]]) -> int:\n",
    "        m,n = len(heightMap), len(heightMap[0])\n",
    "        if m <= 2 or n <= 2:\n",
    "            return 0\n",
    "        cands = set()\n",
    "        for i in range(1, m-1):\n",
    "            for j in range(1, n-1):\n",
    "                cands.add((i,j))\n",
    "        cur = []\n",
    "        for i in range(m):\n",
    "            heapq.heappush(cur, (heightMap[i][0], i, 0))\n",
    "            heapq.heappush(cur, (heightMap[i][n-1], i, n-1))\n",
    "        for j in range(1, n-1):\n",
    "            heapq.heappush(cur, (heightMap[0][j], 0, j))\n",
    "            heapq.heappush(cur, (heightMap[m-1][j], m-1, j))\n",
    "        ret = 0\n",
    "        H = 0\n",
    "        while cands:\n",
    "            short = heapq.heappop(cur)\n",
    "            H = max(H, short[0])\n",
    "            for i,j in ((short[1]-1, short[2]), (short[1]+1, short[2]), (short[1], short[2]-1), (short[1], short[2]+1)):\n",
    "                if (i,j) in cands:\n",
    "                    cands.remove((i,j))\n",
    "                    heapq.heappush(cur, (heightMap[i][j], i,j))\n",
    "                    if heightMap[i][j] < H:\n",
    "                        ret += H - heightMap[i][j]\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import queue\n",
    "class Point:\n",
    "    def __init__(self, x, y, h):\n",
    "        self.x = x\n",
    "        self.y = y\n",
    "        self.h = h\n",
    "    def __lt__(self, other):\n",
    "        return self.h < other.h\n",
    "\n",
    "class Solution:\n",
    "    def trapRainWater(self, hs: List[List[int]]) -> int:\n",
    "        m, n = len(hs), len(hs[0])\n",
    "        if m <= 2 or n <= 2:\n",
    "            return 0\n",
    "        h = []\n",
    "        vs = [[False] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            heapq.heappush(h, Point(i, 0, hs[i][0]))\n",
    "            heapq.heappush(h, Point(i, n-1, hs[i][n-1]))\n",
    "            vs[i][0] = True\n",
    "            vs[i][n-1] = True\n",
    "        for j in range(1, n-1):\n",
    "            heapq.heappush(h, Point(0, j, hs[0][j]))\n",
    "            heapq.heappush(h, Point(m-1, j, hs[m-1][j]))\n",
    "            vs[0][j] = True\n",
    "            vs[m-1][j] = True\n",
    "        # dj\n",
    "        ans = 0\n",
    "        while len(h) > 0:\n",
    "            p = heapq.heappop(h)\n",
    "            x, y, nh = p.x, p.y, p.h\n",
    "            # print(x, y, nh)\n",
    "            for dx, dy in [[0, 1], [0, -1], [1, 0], [-1, 0]]:\n",
    "                # print(dx, dy)\n",
    "                if x+dx>=0 and x+dx<m and y+dy>=0 and y+dy<n and not vs[x+dx][y+dy]:\n",
    "                    vs[x+dx][y+dy] = True\n",
    "                    if hs[x+dx][y+dy] < nh:\n",
    "                        ans += nh-hs[x+dx][y+dy]\n",
    "                        hs[x+dx][y+dy] = nh\n",
    "                    heapq.heappush(h, Point(x+dx, y+dy, hs[x+dx][y+dy]))\n",
    "            \n",
    "        return ans\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.m, self.n = None, None\n",
    "\n",
    "    def neighbours(self, coor):\n",
    "        i, j = coor \n",
    "        res = [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]\n",
    "        return [x for x in res if  self.m > x[0] >= 0 and self.n > x[1] >= 0]\n",
    "\n",
    "    def trapRainWater(self, heightMap) -> int:\n",
    "        m, n = len(heightMap), len(heightMap[0])\n",
    "        if m <= 2 or n <= 2:\n",
    "            return 0\n",
    "        \n",
    "        self.m, self.n = m, n\n",
    "        \n",
    "        from heapq import (heapify, heappush, heappop)\n",
    "        pq = []\n",
    "        heapify(pq)\n",
    "\n",
    "        # isVisited denotes whether elements are visited\n",
    "        isVisited = set()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i == 0 or i == self.m - 1 or j == 0 or j == self.n - 1:\n",
    "                    heappush(pq, (heightMap[i][j], (i, j)))\n",
    "                    isVisited.add((i, j))\n",
    "        \n",
    "        res = 0\n",
    "        while pq:\n",
    "            # 当前外围最低点\n",
    "            water, coor = heappop(pq)\n",
    "            for vecino in self.neighbours(coor):\n",
    "                if vecino not in isVisited:\n",
    "                    nHeight = heightMap[vecino[0]][vecino[1]]\n",
    "                    tmpWater = max(nHeight, water)\n",
    "                    if tmpWater > nHeight:\n",
    "                        res += tmpWater - nHeight\n",
    "                    isVisited.add(vecino)\n",
    "                    heappush(pq, (tmpWater, vecino))\n",
    "        \n",
    "        return res \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def boundary(row: int, column: int, offsets=None):\n",
    "    if offsets is None:\n",
    "        offsets = [(-1, 0), (1, 0), (0, 1), (0, -1)]\n",
    "\n",
    "    def around(r: int, c: int, valid=None):\n",
    "        for dr, dc in offsets:\n",
    "            nr, nc = r + dr, c + dc\n",
    "            if 0 <= nr < row and 0 <= nc < column:\n",
    "                if valid is None or valid(nr, nc):\n",
    "                    yield nr, nc\n",
    "\n",
    "    return around\n",
    "\n",
    "class Solution:\n",
    "    def trapRainWater(self, heights: List[List[int]]) -> int:\n",
    "        m, n = len(heights), len(heights[0])\n",
    "        arr = [(heights[i][j], i, j) for j in range(n) for i in range(m)]\n",
    "        arr.sort(key=lambda it:it[0])\n",
    "\n",
    "        f = list(range(m * n + 1))\n",
    "        cnt = [0] * (m * n + 1)\n",
    "        hs = [0] * (m * n + 1)\n",
    "        ans = 0\n",
    "\n",
    "        def find(i):\n",
    "            if i != f[i]:\n",
    "                f[i] = find(f[i])\n",
    "            return f[i]\n",
    "\n",
    "        def union(i, j, h):\n",
    "            nonlocal ans\n",
    "            fi, fj = find(i), find(j)\n",
    "            if fi != fj:\n",
    "                if fi > fj:\n",
    "                    fi, fj = fj, fi\n",
    "                f[fj] = fi\n",
    "                cnt[fi] += cnt[fj]\n",
    "                hs[fi] += hs[fj]\n",
    "                if fi == 0:\n",
    "                    ans += h * cnt[fj] - hs[fj]\n",
    "\n",
    "        around = boundary(m, n)\n",
    "        for h, i, j in arr:\n",
    "            ij = i * n + j + 1\n",
    "            cnt[ij], hs[ij] = 1, h\n",
    "            for ni, nj in around(i, j):\n",
    "                nij = ni * n + nj + 1\n",
    "                if cnt[nij] > 0:\n",
    "                    union(ij, nij, h)\n",
    "            if i == 0 or j == 0 or i == m - 1 or j == n - 1:\n",
    "                union(0, ij, h)\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    import heapq\n",
    "    def trapRainWater(self, heightMap: List[List[int]]) -> int:\n",
    "        pq = []\n",
    "        heapq.heapify(pq)\n",
    "        n = len(heightMap)\n",
    "        m = len(heightMap[0])\n",
    "\n",
    "        visited = set()\n",
    "        res = 0\n",
    "        x_dirs = [0, 0, 1, -1]\n",
    "        y_dirs = [1, -1, 0, 0]\n",
    "        # first, add add the cells at the peripherie into the queue\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if i == 0 or j == 0 or i == n - 1 or j == m - 1:\n",
    "                    heapq.heappush(pq, (heightMap[i][j], i, j))\n",
    "                    visited.add((i, j))\n",
    "        \n",
    "        while pq:\n",
    "            min_height, x, y = heapq.heappop(pq)\n",
    "            for x_dir, y_dir in zip(x_dirs, y_dirs):\n",
    "                nx = x + x_dir\n",
    "                ny = y + y_dir\n",
    "                if 0 <= nx < n and 0 <= ny < m and (nx, ny) not in visited:\n",
    "                    if heightMap[nx][ny] < min_height:\n",
    "                        res += (min_height - heightMap[nx][ny])\n",
    "                    heapq.heappush(pq, (max(min_height, heightMap[nx][ny]), nx, ny))\n",
    "                    visited.add((nx, ny))\n",
    "\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def boundary(row: int, column: int, offsets=None):\n",
    "    if offsets is None:\n",
    "        offsets = [(-1, 0), (1, 0), (0, 1), (0, -1)]\n",
    "\n",
    "    def around(r: int, c: int, valid=None):\n",
    "        for dr, dc in offsets:\n",
    "            nr, nc = r + dr, c + dc\n",
    "            if 0 <= nr < row and 0 <= nc < column:\n",
    "                if valid is None or valid(nr, nc):\n",
    "                    yield nr, nc\n",
    "\n",
    "    return around\n",
    "\n",
    "class Solution:\n",
    "    def trapRainWater(self, heights: List[List[int]]) -> int:\n",
    "        m, n = len(heights), len(heights[0])\n",
    "        arr = [(heights[i][j], i, j) for j in range(n) for i in range(m)]\n",
    "        arr.sort(key=lambda it:it[0])\n",
    "\n",
    "        f = list(range(m * n + 1))\n",
    "        cnt = [0] * (m * n + 1)\n",
    "        hs = [0] * (m * n + 1)\n",
    "        ans = 0\n",
    "\n",
    "        def find(i):\n",
    "            if i != f[i]:\n",
    "                f[i] = find(f[i])\n",
    "            return f[i]\n",
    "\n",
    "        def union(i, j, h):\n",
    "            nonlocal ans\n",
    "            fi, fj = find(i), find(j)\n",
    "            if fi != fj:\n",
    "                if fi > fj:\n",
    "                    fi, fj = fj, fi\n",
    "                f[fj] = fi\n",
    "                cnt[fi] += cnt[fj]\n",
    "                hs[fi] += hs[fj]\n",
    "                if fi == 0:\n",
    "                    ans += h * cnt[fj] - hs[fj]\n",
    "\n",
    "        around = boundary(m, n)\n",
    "        for h, i, j in arr:\n",
    "            ij = i * n + j + 1\n",
    "            cnt[ij], hs[ij] = 1, h\n",
    "            for ni, nj in around(i, j):\n",
    "                nij = ni * n + nj + 1\n",
    "                if cnt[nij] > 0:\n",
    "                    union(ij, nij, h)\n",
    "            if i == 0 or j == 0 or i == m - 1 or j == n - 1:\n",
    "                union(0, ij, h)\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def boundary(row: int, column: int, offsets=None):\n",
    "    if offsets is None:\n",
    "        offsets = [(-1, 0), (1, 0), (0, 1), (0, -1)]\n",
    "\n",
    "    def around(r: int, c: int, valid=None):\n",
    "        for dr, dc in offsets:\n",
    "            nr, nc = r + dr, c + dc\n",
    "            if 0 <= nr < row and 0 <= nc < column:\n",
    "                if valid is None or valid(nr, nc):\n",
    "                    yield nr, nc\n",
    "\n",
    "    return around\n",
    "\n",
    "class Solution:\n",
    "    def trapRainWater(self, heights: List[List[int]]) -> int:\n",
    "        m, n = len(heights), len(heights[0])\n",
    "        arr = [(heights[i][j], i, j) for j in range(n) for i in range(m)]\n",
    "        arr.sort(key=lambda it:it[0])\n",
    "\n",
    "        f = list(range(m * n + 1))\n",
    "        cnt = [0] * (m * n + 1)\n",
    "        hs = [0] * (m * n + 1)\n",
    "        ans = 0\n",
    "\n",
    "        def find(i):\n",
    "            if i != f[i]:\n",
    "                f[i] = find(f[i])\n",
    "            return f[i]\n",
    "\n",
    "        def union(i, j, h):\n",
    "            nonlocal ans\n",
    "            fi, fj = find(i), find(j)\n",
    "            if fi != fj:\n",
    "                if fi > fj:\n",
    "                    fi, fj = fj, fi\n",
    "                f[fj] = fi\n",
    "                cnt[fi] += cnt[fj]\n",
    "                hs[fi] += hs[fj]\n",
    "                if fi == 0:\n",
    "                    ans += h * cnt[fj] - hs[fj]\n",
    "\n",
    "        around = boundary(m, n)\n",
    "        for h, i, j in arr:\n",
    "            ij = i * n + j + 1\n",
    "            cnt[ij], hs[ij] = 1, h\n",
    "            for ni, nj in around(i, j):\n",
    "                nij = ni * n + nj + 1\n",
    "                if cnt[nij] > 0:\n",
    "                    union(ij, nij, h)\n",
    "            if i == 0 or j == 0 or i == m - 1 or j == n - 1:\n",
    "                union(0, ij, h)\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def boundary(row: int, column: int, offsets=None):\n",
    "    if offsets is None:\n",
    "        offsets = [(-1, 0), (1, 0), (0, 1), (0, -1)]\n",
    "\n",
    "    def around(r: int, c: int, valid=None):\n",
    "        for dr, dc in offsets:\n",
    "            nr, nc = r + dr, c + dc\n",
    "            if 0 <= nr < row and 0 <= nc < column:\n",
    "                if valid is None or valid(nr, nc):\n",
    "                    yield nr, nc\n",
    "\n",
    "    return around\n",
    "\n",
    "class Solution:\n",
    "    def trapRainWater(self, heights: List[List[int]]) -> int:\n",
    "        m, n = len(heights), len(heights[0])\n",
    "        arr = [(heights[i][j], i, j) for j in range(n) for i in range(m)]\n",
    "        arr.sort(key=lambda it:it[0])\n",
    "\n",
    "        f = list(range(m * n + 1))\n",
    "        cnt = [0] * (m * n + 1)\n",
    "        hs = [0] * (m * n + 1)\n",
    "        ans = 0\n",
    "\n",
    "        def find(i):\n",
    "            if i != f[i]:\n",
    "                f[i] = find(f[i])\n",
    "            return f[i]\n",
    "\n",
    "        def union(i, j, h):\n",
    "            nonlocal ans\n",
    "            fi, fj = find(i), find(j)\n",
    "            if fi != fj:\n",
    "                if fi > fj:\n",
    "                    fi, fj = fj, fi\n",
    "                f[fj] = fi\n",
    "                cnt[fi] += cnt[fj]\n",
    "                hs[fi] += hs[fj]\n",
    "                if fi == 0:\n",
    "                    ans += h * cnt[fj] - hs[fj]\n",
    "\n",
    "        around = boundary(m, n)\n",
    "        for h, i, j in arr:\n",
    "            ij = i * n + j + 1\n",
    "            cnt[ij], hs[ij] = 1, h\n",
    "            for ni, nj in around(i, j):\n",
    "                nij = ni * n + nj + 1\n",
    "                if cnt[nij] > 0:\n",
    "                    union(ij, nij, h)\n",
    "            if i == 0 or j == 0 or i == m - 1 or j == n - 1:\n",
    "                union(0, ij, h)\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def boundary(row: int, column: int, offsets=None):\n",
    "    if offsets is None:\n",
    "        offsets = [(-1, 0), (1, 0), (0, 1), (0, -1)]\n",
    "\n",
    "    def around(r: int, c: int, valid=None):\n",
    "        for dr, dc in offsets:\n",
    "            nr, nc = r + dr, c + dc\n",
    "            if 0 <= nr < row and 0 <= nc < column:\n",
    "                if valid is None or valid(nr, nc):\n",
    "                    yield nr, nc\n",
    "\n",
    "    return around\n",
    "\n",
    "class Solution:\n",
    "    def trapRainWater(self, heights: List[List[int]]) -> int:\n",
    "        m, n = len(heights), len(heights[0])\n",
    "        arr = [(heights[i][j], i, j) for j in range(n) for i in range(m)]\n",
    "        arr.sort(key=lambda it:it[0])\n",
    "\n",
    "        f = list(range(m * n + 1))\n",
    "        cnt = [0] * (m * n + 1)\n",
    "        hs = [0] * (m * n + 1)\n",
    "        ans = 0\n",
    "\n",
    "        def find(i):\n",
    "            if i != f[i]:\n",
    "                f[i] = find(f[i])\n",
    "            return f[i]\n",
    "\n",
    "        def union(i, j, h):\n",
    "            nonlocal ans\n",
    "            fi, fj = find(i), find(j)\n",
    "            if fi != fj:\n",
    "                if fi > fj:\n",
    "                    fi, fj = fj, fi\n",
    "                f[fj] = fi\n",
    "                cnt[fi] += cnt[fj]\n",
    "                hs[fi] += hs[fj]\n",
    "                if fi == 0:\n",
    "                    ans += h * cnt[fj] - hs[fj]\n",
    "\n",
    "        around = boundary(m, n)\n",
    "        for h, i, j in arr:\n",
    "            ij = i * n + j + 1\n",
    "            cnt[ij], hs[ij] = 1, h\n",
    "            for ni, nj in around(i, j):\n",
    "                nij = ni * n + nj + 1\n",
    "                if cnt[nij] > 0:\n",
    "                    union(ij, nij, h)\n",
    "            if i == 0 or j == 0 or i == m - 1 or j == n - 1:\n",
    "                union(0, ij, h)\n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import queue\n",
    "class Point:\n",
    "    def __init__(self, x, y, h):\n",
    "        self.x = x\n",
    "        self.y = y\n",
    "        self.h = h\n",
    "    def __lt__(self, other):\n",
    "        return self.h < other.h\n",
    "\n",
    "class Solution:\n",
    "    def trapRainWater(self, hs: List[List[int]]) -> int:\n",
    "        m, n = len(hs), len(hs[0])\n",
    "        if m <= 2 or n <= 2:\n",
    "            return 0\n",
    "        h = queue.PriorityQueue()\n",
    "        vs = [[False] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            h.put(Point(i, 0, hs[i][0]))\n",
    "            h.put(Point(i, n-1, hs[i][n-1]))\n",
    "            vs[i][0] = True\n",
    "            vs[i][n-1] = True\n",
    "        for j in range(1, n-1):\n",
    "            h.put(Point(0, j, hs[0][j]))\n",
    "            h.put(Point(m-1, j, hs[m-1][j]))\n",
    "            vs[0][j] = True\n",
    "            vs[m-1][j] = True\n",
    "        # dj\n",
    "        ans = 0\n",
    "        while not h.empty():\n",
    "            p = h.get()\n",
    "            x, y, nh = p.x, p.y, p.h\n",
    "            # print(x, y, nh)\n",
    "            for dx, dy in [[0, 1], [0, -1], [1, 0], [-1, 0]]:\n",
    "                print(dx, dy)\n",
    "                if x+dx>=0 and x+dx<m and y+dy>=0 and y+dy<n and not vs[x+dx][y+dy]:\n",
    "                    vs[x+dx][y+dy] = True\n",
    "                    if hs[x+dx][y+dy] < nh:\n",
    "                        ans += nh-hs[x+dx][y+dy]\n",
    "                        hs[x+dx][y+dy] = nh\n",
    "                    h.put(Point(x+dx, y+dy, hs[x+dx][y+dy]))\n",
    "            \n",
    "        return ans\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trapRainWater(self, heightMap: List[List[int]]) -> int:\n",
    "        m, n = len(heightMap), len(heightMap[0])\n",
    "        stack = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i in [0, m-1] or j in [0, n-1]:\n",
    "                    stack.append([0, i, j])\n",
    "        \n",
    "        visit = defaultdict(lambda: float(\"inf\"))\n",
    "        ans = 0\n",
    "        while stack:\n",
    "            dis, i, j = heapq.heappop(stack)\n",
    "            if visit[(i, j)] <= dis:\n",
    "                continue\n",
    "            ans += max(0, dis-heightMap[i][j])\n",
    "            visit[(i, j)] = dis\n",
    "            for x, y in [[i-1, j], [i+1, j], [i, j-1], [i, j+1]]:\n",
    "                if 0<=x<m and 0<=y<n:\n",
    "                    heapq.heappush(stack, [max(dis, heightMap[i][j]), x, y])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trapRainWater(self, heightMap: List[List[int]]) -> int:\n",
    "        def is_valid(x, y):\n",
    "            return 0 <= x < s1 and 0 <= y < s2\n",
    "\n",
    "        s1, s2 = len(heightMap), len(heightMap[0])\n",
    "        s = s1 * s2\n",
    "\n",
    "        if s1 <= 2 or s2 <= 2:\n",
    "            return 0\n",
    "\n",
    "        wall_list = []\n",
    "        for i1 in range(0, s1):\n",
    "            wall_list.append((i1, 0))\n",
    "            wall_list.append((i1, s2 - 1))\n",
    "        for i2 in range(0, s2):\n",
    "            wall_list.append((0, i2))\n",
    "            wall_list.append((s1 - 1, i2))\n",
    "\n",
    "        visited = set()\n",
    "        heap = []\n",
    "        for i1, i2 in wall_list:\n",
    "            heap.append((heightMap[i1][i2], i1, i2))\n",
    "            visited.add((i1, i2))\n",
    "\n",
    "        heapq.heapify(heap)\n",
    "\n",
    "        now_height = 0\n",
    "\n",
    "        ans = 0\n",
    "        while len(visited) < s:\n",
    "            height, i1, i2 = heapq.heappop(heap)\n",
    "\n",
    "            now_height = max(now_height, height)\n",
    "\n",
    "            neighbours = [(i1 + 1, i2), (i1 - 1, i2), (i1, i2 + 1), (i1, i2 - 1)]\n",
    "\n",
    "            inners = [neighbour for neighbour in neighbours if\n",
    "                      (is_valid(neighbour[0], neighbour[1]) and neighbour not in visited)]\n",
    "\n",
    "            for ii1, ii2 in inners:\n",
    "                if heightMap[ii1][ii2] < now_height:\n",
    "                    ans += now_height - heightMap[ii1][ii2]\n",
    "\n",
    "                heapq.heappush(heap, (heightMap[ii1][ii2], ii1, ii2))\n",
    "                visited.add((ii1, ii2))\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trapRainWater(self, heights: List[List[int]]) -> int:\n",
    "        def boundary(row: int, column: int):\n",
    "            # if offsets is None:\n",
    "            offsets = [(-1, 0), (1, 0), (0, 1), (0, -1)]\n",
    "\n",
    "            def around(r: int, c: int):\n",
    "                for dr, dc in offsets:\n",
    "                    nr, nc = r + dr, c + dc\n",
    "                    if 0 <= nr < row and 0 <= nc < column:\n",
    "                        yield nr, nc\n",
    "\n",
    "            return around\n",
    "\n",
    "        m, n = len(heights), len(heights[0])\n",
    "        arr = [(heights[i][j], i, j) for j in range(n) for i in range(m)]\n",
    "        arr.sort(key=lambda it:it[0])\n",
    "\n",
    "        f = list(range(m * n + 1))\n",
    "        cnt = [0] * (m * n + 1)\n",
    "        hs = [0] * (m * n + 1)\n",
    "        ans = 0\n",
    "\n",
    "        def find(i):\n",
    "            if i != f[i]:\n",
    "                f[i] = find(f[i])\n",
    "            return f[i]\n",
    "\n",
    "        def union(i, j, h):\n",
    "            nonlocal ans\n",
    "            fi, fj = find(i), find(j)\n",
    "            if fi != fj:\n",
    "                if fi > fj:\n",
    "                    fi, fj = fj, fi\n",
    "                f[fj] = fi\n",
    "                cnt[fi] += cnt[fj]\n",
    "                hs[fi] += hs[fj]\n",
    "                if fi == 0:\n",
    "                    ans += h * cnt[fj] - hs[fj]\n",
    "\n",
    "        around = boundary(m, n)\n",
    "        for h, i, j in arr:\n",
    "            ij = i * n + j + 1\n",
    "            cnt[ij], hs[ij] = 1, h\n",
    "            for ni, nj in around(i, j):\n",
    "                nij = ni * n + nj + 1\n",
    "                if cnt[nij] > 0:\n",
    "                    union(ij, nij, h)\n",
    "            if i == 0 or j == 0 or i == m - 1 or j == n - 1:\n",
    "                union(0, ij, h)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def boundary(row: int, column: int, offsets=None):\n",
    "    if offsets is None:\n",
    "        offsets = [(-1, 0), (1, 0), (0, 1), (0, -1)]\n",
    "\n",
    "    def around(r: int, c: int, valid=None):\n",
    "        for dr, dc in offsets:\n",
    "            nr, nc = r + dr, c + dc\n",
    "            if 0 <= nr < row and 0 <= nc < column:\n",
    "                if valid is None or valid(nr, nc):\n",
    "                    yield nr, nc\n",
    "\n",
    "    return around\n",
    "\n",
    "class Solution:\n",
    "    def trapRainWater(self, heights: List[List[int]]) -> int:\n",
    "        m, n = len(heights), len(heights[0])\n",
    "        arr = [(heights[i][j], i, j) for j in range(n) for i in range(m)]\n",
    "        arr.sort(key=lambda it:it[0])\n",
    "\n",
    "        f = list(range(m * n + 1))\n",
    "        cnt = [0] * (m * n + 1)\n",
    "        hs = [0] * (m * n + 1)\n",
    "        ans = 0\n",
    "\n",
    "        def find(i):\n",
    "            if i != f[i]:\n",
    "                f[i] = find(f[i])\n",
    "            return f[i]\n",
    "\n",
    "        def union(i, j, h):\n",
    "            nonlocal ans\n",
    "            fi, fj = find(i), find(j)\n",
    "            if fi != fj:\n",
    "                if fi > fj:\n",
    "                    fi, fj = fj, fi\n",
    "                f[fj] = fi\n",
    "                cnt[fi] += cnt[fj]\n",
    "                hs[fi] += hs[fj]\n",
    "                if fi == 0:\n",
    "                    ans += h * cnt[fj] - hs[fj]\n",
    "\n",
    "        around = boundary(m, n)\n",
    "        for h, i, j in arr:\n",
    "            ij = i * n + j + 1\n",
    "            cnt[ij], hs[ij] = 1, h\n",
    "            for ni, nj in around(i, j):\n",
    "                nij = ni * n + nj + 1\n",
    "                if cnt[nij] > 0:\n",
    "                    union(ij, nij, h)\n",
    "            if i == 0 or j == 0 or i == m - 1 or j == n - 1:\n",
    "                union(0, ij, h)\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import queue\n",
    "class Point:\n",
    "    def __init__(self, x, y, h):\n",
    "        self.x = x\n",
    "        self.y = y\n",
    "        self.h = h\n",
    "    def __lt__(self, other):\n",
    "        return self.h < other.h\n",
    "\n",
    "class Solution:\n",
    "    def trapRainWater(self, hs: List[List[int]]) -> int:\n",
    "        m, n = len(hs), len(hs[0])\n",
    "        if m <= 2 or n <= 2:\n",
    "            return 0\n",
    "        h = []\n",
    "        vs = [[False] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            heapq.heappush(h, Point(i, 0, hs[i][0]))\n",
    "            heapq.heappush(h, Point(i, n-1, hs[i][n-1]))\n",
    "            vs[i][0] = True\n",
    "            vs[i][n-1] = True\n",
    "        for j in range(1, n-1):\n",
    "            heapq.heappush(h, Point(0, j, hs[0][j]))\n",
    "            heapq.heappush(h, Point(m-1, j, hs[m-1][j]))\n",
    "            vs[0][j] = True\n",
    "            vs[m-1][j] = True\n",
    "        # dj\n",
    "        ans = 0\n",
    "        while len(h) > 0:\n",
    "            p = heapq.heappop(h)\n",
    "            x, y, nh = p.x, p.y, p.h\n",
    "            # print(x, y, nh)\n",
    "            for dx, dy in [[0, 1], [0, -1], [1, 0], [-1, 0]]:\n",
    "                # print(dx, dy)\n",
    "                if x+dx>=0 and x+dx<m and y+dy>=0 and y+dy<n and not vs[x+dx][y+dy]:\n",
    "                    vs[x+dx][y+dy] = True\n",
    "                    if hs[x+dx][y+dy] < nh:\n",
    "                        ans += nh-hs[x+dx][y+dy]\n",
    "                        hs[x+dx][y+dy] = nh\n",
    "                    heapq.heappush(h, Point(x+dx, y+dy, hs[x+dx][y+dy]))\n",
    "            \n",
    "        return ans\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trapRainWater(self, heightMap: List[List[int]]) -> int:\n",
    "        myheap = []\n",
    "        visit = set()\n",
    "        m = len(heightMap)\n",
    "        n = len(heightMap[0])\n",
    "        if m<=2 or n<=2:\n",
    "            return 0\n",
    "        for i in range(m):\n",
    "            heapq.heappush(myheap, (heightMap[i][0], i, 0))\n",
    "            visit.add((i,0))\n",
    "            heapq.heappush(myheap, (heightMap[i][n-1], i, n-1))\n",
    "            visit.add((i,n-1))\n",
    "        for j in range(n):\n",
    "            heapq.heappush(myheap, (heightMap[0][j], 0, j))\n",
    "            visit.add((0,j))\n",
    "            heapq.heappush(myheap, (heightMap[m-1][j], m-1, j))\n",
    "            visit.add((m-1,j))\n",
    "        ans = 0\n",
    "        while myheap:\n",
    "            nowHeight, i, j = heapq.heappop(myheap)\n",
    "            for x,y in [(i-1,j),(i+1,j),(i,j-1),(i,j+1)]:\n",
    "                if 0<=x<m and 0<=y<n and (x,y) not in visit:\n",
    "                    visit.add((x,y))\n",
    "                    maxHeight = max(nowHeight, heightMap[x][y])\n",
    "                    ans += maxHeight - heightMap[x][y]\n",
    "                    heapq.heappush(myheap,(maxHeight,x,y))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import queue\n",
    "class Point:\n",
    "    def __init__(self, x, y, h):\n",
    "        self.x = x\n",
    "        self.y = y\n",
    "        self.h = h\n",
    "    def __lt__(self, other):\n",
    "        return self.h < other.h\n",
    "\n",
    "class Solution:\n",
    "    def trapRainWater(self, hs: List[List[int]]) -> int:\n",
    "        m, n = len(hs), len(hs[0])\n",
    "        if m <= 2 or n <= 2:\n",
    "            return 0\n",
    "        h = queue.PriorityQueue()\n",
    "        vs = [[False] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            h.put(Point(i, 0, hs[i][0]))\n",
    "            h.put(Point(i, n-1, hs[i][n-1]))\n",
    "            vs[i][0] = True\n",
    "            vs[i][n-1] = True\n",
    "        for j in range(1, n-1):\n",
    "            h.put(Point(0, j, hs[0][j]))\n",
    "            h.put(Point(m-1, j, hs[m-1][j]))\n",
    "            vs[0][j] = True\n",
    "            vs[m-1][j] = True\n",
    "        # dj\n",
    "        ans = 0\n",
    "        while not h.empty():\n",
    "            p = h.get()\n",
    "            x, y, nh = p.x, p.y, p.h\n",
    "            # print(x, y, nh)\n",
    "            for dx, dy in [[0, 1], [0, -1], [1, 0], [-1, 0]]:\n",
    "                print(dx, dy)\n",
    "                if x+dx>=0 and x+dx<m and y+dy>=0 and y+dy<n and not vs[x+dx][y+dy]:\n",
    "                    vs[x+dx][y+dy] = True\n",
    "                    if hs[x+dx][y+dy] < nh:\n",
    "                        ans += nh-hs[x+dx][y+dy]\n",
    "                        hs[x+dx][y+dy] = nh\n",
    "                    h.put(Point(x+dx, y+dy, hs[x+dx][y+dy]))\n",
    "            \n",
    "        return ans\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trapRainWater(self, heightMap: List[List[int]]) -> int:\n",
    "        res = 0\n",
    "        heap = []\n",
    "        h, w = len(heightMap), len(heightMap[0])\n",
    "        visited = set()\n",
    "        for i in range(h):\n",
    "            if (i, 0) not in visited:\n",
    "                visited.add((i, 0))\n",
    "                heapq.heappush(heap, (heightMap[i][0], i, 0))\n",
    "            if (i, w-1) not in visited:\n",
    "                visited.add((i, w-1))\n",
    "                heapq.heappush(heap, (heightMap[i][w-1], i, w-1))\n",
    "\n",
    "        for i in range(w):\n",
    "            if (0, i) not in visited:\n",
    "                visited.add((0, i))\n",
    "                heapq.heappush(heap, (heightMap[0][i], 0, i))\n",
    "            if (h-1, i) not in visited:\n",
    "                visited.add((h-1, i))\n",
    "                heapq.heappush(heap, (heightMap[h-1][i], h-1, i))\n",
    "        \n",
    "        moves = [0, 1, 0, -1, 0]\n",
    "        while(len(visited) < h*w):\n",
    "            num, x, y = heapq.heappop(heap)\n",
    "            for i in range(4):\n",
    "                new_x, new_y = x + moves[i], y + moves[i+1]\n",
    "                if 0 <= new_x < h and 0 <= new_y < w and (new_x, new_y) not in visited:\n",
    "                    res += max(0, num - heightMap[new_x][new_y])\n",
    "                    visited.add((new_x, new_y))\n",
    "                    heapq.heappush(heap, (max(num, heightMap[new_x][new_y]), new_x, new_y))\n",
    "        \n",
    "        return res\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trapRainWater(self, heightMap: List[List[int]]) -> int:\n",
    "        if not heightMap:\n",
    "            return 0\n",
    "        \n",
    "        m, n = len(heightMap), len(heightMap[0])\n",
    "        heap = []\n",
    "        visited = set()\n",
    "        res = 0\n",
    "        \n",
    "        # Add all the boundary cells to the heap\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i == 0 or i == m-1 or j == 0 or j == n-1:\n",
    "                    heapq.heappush(heap, (heightMap[i][j], i, j))\n",
    "                    visited.add((i, j))\n",
    "        \n",
    "        # Process the heap\n",
    "        while heap:\n",
    "            height, i, j = heapq.heappop(heap)\n",
    "            \n",
    "            # Check all the neighbors\n",
    "            for x, y in [(i+1, j), (i-1, j), (i, j+1), (i, j-1)]:\n",
    "                if 0 <= x < m and 0 <= y < n and (x, y) not in visited:\n",
    "                    visited.add((x, y))\n",
    "                    res += max(0, height - heightMap[x][y])\n",
    "                    heapq.heappush(heap, (max(heightMap[x][y], height), x, y))\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class PQ:\n",
    "    def __init__(self):\n",
    "        self.queue = []\n",
    "        self.size = 0\n",
    "    \n",
    "\n",
    "    def top(self):\n",
    "        if self.size != 0:\n",
    "            return self.queue[0]\n",
    "        return None\n",
    "    \n",
    "    def push(self, x):\n",
    "        # x => (int, int)\n",
    "        if self.size < len(self.queue):\n",
    "            self.queue[self.size] = x\n",
    "        else:\n",
    "            self.queue.append(x)\n",
    "        self.size += 1\n",
    "        #    0\n",
    "        #  1  2\n",
    "        # 3 4 5 6\n",
    "        child = self.size - 1\n",
    "        parent = (self.size - 2) // 2\n",
    "        while parent >= 0 and self.queue[child][0] < self.queue[parent][0]:\n",
    "            self.queue[child], self.queue[parent] = self.queue[parent], self.queue[child]\n",
    "            child = parent\n",
    "            parent = (parent - 1) // 2\n",
    "\n",
    "    def pop(self):\n",
    "        res = self.top()\n",
    "        if res:\n",
    "            self.size = self.size - 1\n",
    "            self.queue[0] = self.queue[self.size] \n",
    "            cur = 0\n",
    "            left = cur * 2 + 1\n",
    "            right = cur * 2 + 2\n",
    "            while left < self.size:\n",
    "                if right < self.size and self.queue[right][0] < self.queue[left][0]:\n",
    "                    smaller = right\n",
    "                else:\n",
    "                    smaller = left\n",
    "                if self.queue[cur][0] > self.queue[smaller][0]:\n",
    "                    self.queue[cur], self.queue[smaller] = self.queue[smaller], self.queue[cur]\n",
    "                    cur = smaller\n",
    "                    left = cur * 2 + 1\n",
    "                    right = cur * 2 + 2\n",
    "                else:\n",
    "                    break\n",
    "        return res\n",
    "\n",
    "class Solution:\n",
    "    def trapRainWater(self, heightMap: List[List[int]]) -> int:\n",
    "        m = len(heightMap)\n",
    "        if m <= 2:\n",
    "            return 0\n",
    "        n = len(heightMap[0])\n",
    "        if n <= 2:\n",
    "            return 0\n",
    "        pq = PQ()\n",
    "        visited = [[False for _ in range(n)] for _ in range(m)]\n",
    "        for i in range(n):\n",
    "            if not visited[0][i]:\n",
    "                visited[0][i] = True\n",
    "                pq.push((heightMap[0][i], i))\n",
    "            if not visited[m - 1][i]:\n",
    "                visited[m - 1][i] = True\n",
    "                pq.push((heightMap[m - 1][i], (m - 1) * n + i))\n",
    "        for i in range(m):\n",
    "            if not visited[i][0]:\n",
    "                visited[i][0] = True\n",
    "                pq.push((heightMap[i][0], i * n))\n",
    "            if not visited[i][n - 1]:\n",
    "                visited[i][n - 1] = True\n",
    "                pq.push((heightMap[i][n - 1], i * n + n - 1))\n",
    "\n",
    "        dir = [-1, 0, 1, 0]\n",
    "        res = 0\n",
    "        while pq.size > 0:\n",
    "            height, idx = pq.pop()\n",
    "            i, j = idx // n, idx % n\n",
    "            for k in range(4):\n",
    "                x, y = dir[k], dir[(k + 1) % 4]\n",
    "                i_, j_ = i + x, j + y\n",
    "                if 0 <= i_ < m and 0 <= j_ < n and not visited[i_][j_]:\n",
    "                    diff = max(0, height - heightMap[i_][j_])\n",
    "                    if diff > 0:\n",
    "                        res += diff\n",
    "                        heightMap[i_][j_] = heightMap[i_][j_] + diff\n",
    "                    pq.push((heightMap[i_][j_], i_ * n + j_))\n",
    "                    visited[i_][j_] = True\n",
    "        return res\n",
    "\n",
    "\n",
    "                \n",
    "            \n",
    "            \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trapRainWater(self, heightMap: List[List[int]]) -> int:\n",
    "        m, n = len(heightMap), len(heightMap[0])\n",
    "        from heapq import heappush, heappop\n",
    "        pq = []\n",
    "        visited = set()\n",
    "        for i in range(m):\n",
    "            heappush(pq, [heightMap[i][0], i, 0])\n",
    "            heappush(pq, [heightMap[i][n-1], i, n-1])\n",
    "            visited.add((i, 0))\n",
    "            visited.add((i, n-1))\n",
    "    \n",
    "        for j in range(1, n-1):\n",
    "            heappush(pq, [heightMap[0][j], 0, j])\n",
    "            heappush(pq, [heightMap[m-1][j], m-1, j])\n",
    "            visited.add((0, j))\n",
    "            visited.add((m-1, j))\n",
    "        check = lambda x, y: 0 <= x < m and  0 <= y <n and (x,y) not in visited\n",
    "        direction = [\n",
    "            [-1, 0],\n",
    "            [1, 0],\n",
    "            [0, -1],\n",
    "            [0, 1]\n",
    "        ]\n",
    "        max_height = 0\n",
    "        ans = 0\n",
    "        while pq:\n",
    "            h, x, y = heappop(pq)\n",
    "            if h > max_height:\n",
    "                max_height = h\n",
    "            else:\n",
    "                ans += (max_height-h)\n",
    "            for dx, dy in direction:\n",
    "                newx, newy = x+dx, y+dy\n",
    "                if check(newx, newy):\n",
    "                    visited.add((newx, newy))\n",
    "                    heappush(pq, [heightMap[newx][newy], newx, newy])\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trapRainWater(self, heightMap: List[List[int]]) -> int:\n",
    "        m, n = len(heightMap), len(heightMap[0])\n",
    "        from heapq import heappush, heappop\n",
    "        pq = []\n",
    "        visited = set()\n",
    "        for i in range(m):\n",
    "            heappush(pq, [heightMap[i][0], i, 0])\n",
    "            heappush(pq, [heightMap[i][n-1], i, n-1])\n",
    "            visited.add((i, 0))\n",
    "            visited.add((i, n-1))\n",
    "    \n",
    "        for j in range(1, n-1):\n",
    "            heappush(pq, [heightMap[0][j], 0, j])\n",
    "            heappush(pq, [heightMap[m-1][j], m-1, j])\n",
    "            visited.add((0, j))\n",
    "            visited.add((m-1, j))\n",
    "        check = lambda x, y: 0 <= x < m and  0 <= y <n and (x,y) not in visited\n",
    "        direction = [\n",
    "            [-1, 0],\n",
    "            [1, 0],\n",
    "            [0, -1],\n",
    "            [0, 1]\n",
    "        ]\n",
    "        max_height = 0\n",
    "        ans = 0\n",
    "        while pq:\n",
    "            h, x, y = heappop(pq)\n",
    "            if h > max_height:\n",
    "                max_height = h\n",
    "            else:\n",
    "                ans += (max_height-h)\n",
    "            for dx, dy in direction:\n",
    "                newx, newy = x+dx, y+dy\n",
    "                if check(newx, newy):\n",
    "                    visited.add((newx, newy))\n",
    "                    heappush(pq, [heightMap[newx][newy], newx, newy])\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trapRainWater(self, heightMap: List[List[int]]) -> int:\n",
    "        rows, cols = len(heightMap), len(heightMap[0])\n",
    "        pq, visited = [], set()\n",
    "        for i in range(cols):\n",
    "            heapq.heappush(pq, (heightMap[0][i], 0, i))\n",
    "            heapq.heappush(pq, (heightMap[-1][i], rows-1, i))\n",
    "            visited.add((0,i))\n",
    "            visited.add((rows-1, i))\n",
    "        for i in range(1, rows-1):\n",
    "            heapq.heappush(pq, (heightMap[i][0], i, 0))\n",
    "            heapq.heappush(pq, (heightMap[i][cols-1], i, cols-1))\n",
    "            visited.add((i,0))\n",
    "            visited.add((i,cols-1))\n",
    "\n",
    "        res, maximum = 0, 0 \n",
    "        directions = [(1,0),(0,1),(0,-1),(-1,0)]\n",
    "        while pq:\n",
    "            h, r, c = heapq.heappop(pq)\n",
    "            if h > maximum:\n",
    "                maximum = h \n",
    "            for i, j in directions:\n",
    "                row, col = r + i, c + j \n",
    "                if row < 0 or row >= rows or col < 0 or col >= cols or (row, col) in visited:\n",
    "                    continue \n",
    "                if heightMap[row][col] < maximum:\n",
    "                    res += maximum - heightMap[row][col]\n",
    "                visited.add((row, col))\n",
    "                heapq.heappush(pq, (heightMap[row][col], row, col))\n",
    "        return res \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def valide(self, tgtx, tgty):\n",
    "        if tgtx >= self.n or tgtx < 0:\n",
    "            return False\n",
    "        if tgty >= self.m or tgty < 0:\n",
    "            return False\n",
    "        return True\n",
    "    def trapRainWater(self, heightMap: List[List[int]]) -> int:\n",
    "        self.n = len(heightMap)\n",
    "        self.m = len(heightMap[0])\n",
    "        search_list = []\n",
    "        ans = [[0 for i in range(len(heightMap[0]))] for j in range(len(heightMap))] \n",
    "        flag = [[False for i in range(len(heightMap[0]))] for j in range(len(heightMap))] \n",
    "        for i in range(len(heightMap)):\n",
    "            for j in range(len(heightMap[i])):\n",
    "                search_list.append((i,j))\n",
    "                if i ==0 or i == self.n - 1 or j == 0 or j == self.m-1:\n",
    "                    ans[i][j] = heightMap[i][j]\n",
    "                else:\n",
    "                    ans[i][j] = 9999999\n",
    "        head = 0\n",
    "        directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]\n",
    "        while head < len(search_list):\n",
    "            # print(search_list)\n",
    "            curr_x, curr_y = search_list[head]\n",
    "            flag[curr_x][curr_y] = True \n",
    "            for direction in directions:\n",
    "                tgt_x, tgt_y = curr_x + direction[0], curr_y + direction[1]\n",
    "                if self.valide(tgt_x, tgt_y):\n",
    "                    if ans[curr_x][curr_y] < ans[tgt_x][tgt_y] and ans[tgt_x][tgt_y] > heightMap[tgt_x][tgt_y]:\n",
    "                        ans[tgt_x][tgt_y] = max(ans[curr_x][curr_y], heightMap[tgt_x][tgt_y])\n",
    "                        if flag[tgt_x][tgt_y]:\n",
    "                            flag[tgt_x][tgt_y] = False\n",
    "                            search_list.append((tgt_x, tgt_y))\n",
    "            head += 1\n",
    "        # print(ans)\n",
    "        final_ans = 0\n",
    "        for i in range(len(ans)):\n",
    "            for j in range(len(ans[0])):\n",
    "                final_ans += ans[i][j] - heightMap[i][j]\n",
    "        return final_ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trapRainWater(self, heightMap: List[List[int]]) -> int:\n",
    "        import heapq\n",
    "        if not heightMap: return 0\n",
    "        heap = []\n",
    "        cur_max = float(\"-inf\")\n",
    "        visited = set()\n",
    "        row = len(heightMap)\n",
    "        col = len(heightMap[0])\n",
    "        res = 0\n",
    "        # 边界放进去\n",
    "        # 行\n",
    "        for j in range(col):\n",
    "            heapq.heappush(heap, [heightMap[0][j], 0, j])\n",
    "            heapq.heappush(heap, [heightMap[row - 1][j], row - 1, j])\n",
    "            visited.add((0, j))\n",
    "            visited.add((row - 1, j))\n",
    "        # 列\n",
    "        for i in range(row):\n",
    "            heapq.heappush(heap, [heightMap[i][0], i, 0])\n",
    "            heapq.heappush(heap, [heightMap[i][col - 1], i, col - 1])\n",
    "            visited.add((i, 0))\n",
    "            visited.add((i, col - 1))\n",
    "\n",
    "        while heap:\n",
    "            h, i, j = heapq.heappop(heap)\n",
    "            cur_max = max(h, cur_max)\n",
    "            for x, y in [[-1, 0], [1, 0], [0, 1], [0, -1]]:\n",
    "                tmp_i = i + x\n",
    "                tmp_j = j + y\n",
    "                if tmp_i < 0 or tmp_i >= row or tmp_j < 0 or tmp_j >= col or (tmp_i, tmp_j) in visited:\n",
    "                    continue\n",
    "                visited.add((tmp_i, tmp_j))\n",
    "                if heightMap[tmp_i][tmp_j] < cur_max:\n",
    "                    res += cur_max - heightMap[tmp_i][tmp_j]\n",
    "                heapq.heappush(heap, [heightMap[tmp_i][tmp_j], tmp_i, tmp_j])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def trapRainWater(self, heightMap: List[List[int]]) -> int:\n",
    "        m, n = len(heightMap), len(heightMap[0])\n",
    "        if m <= 2 or n <= 2:\n",
    "            return 0\n",
    "        visited = set()\n",
    "        heap = []\n",
    "        for x in [0, m-1]:\n",
    "            for y in range(n):\n",
    "                heap.append((heightMap[x][y], x, y))\n",
    "                visited.add((x,y))\n",
    "        for y in [0, n-1]:\n",
    "            for x in range(1, m-1):\n",
    "                heap.append((heightMap[x][y], x, y))\n",
    "                visited.add((x,y))\n",
    "        heapq.heapify(heap)\n",
    "        ans = 0\n",
    "        level = 0\n",
    "        while heap:\n",
    "            l, x, y = heapq.heappop(heap)\n",
    "            level = max(level, l)\n",
    "            for dx, dy in [[-1,0],[1,0],[0,1],[0,-1]]:\n",
    "                nx, ny = x+dx, y+dy\n",
    "                if 0<=nx<m and 0<=ny<n and (nx, ny) not in visited:\n",
    "                    visited.add((nx,ny))\n",
    "                    ans += max(0, level-heightMap[nx][ny])\n",
    "                    heapq.heappush(heap, (heightMap[nx][ny], nx, ny))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trapRainWater(self, heightMap: List[List[int]]) -> int:\n",
    "        q = []\n",
    "        res = 0\n",
    "        heapq.heapify(q)\n",
    "        vis = set()\n",
    "        for i in range(len(heightMap)):\n",
    "            heapq.heappush(q, (heightMap[i][0], i, 0))\n",
    "            heapq.heappush(q, (heightMap[i][-1], i, len(heightMap[0])-1))\n",
    "            vis.add((i,0))\n",
    "            vis.add((i,len(heightMap[0])-1))\n",
    "            \n",
    "        for j in range(len(heightMap[0])):\n",
    "            heapq.heappush(q, (heightMap[0][j], 0, j))\n",
    "            heapq.heappush(q, (heightMap[-1][j], len(heightMap)-1, j))\n",
    "            vis.add((0,j))\n",
    "            vis.add((len(heightMap)-1, j))\n",
    "            \n",
    "        ans = 0\n",
    "        print(q)\n",
    "        while q:\n",
    "            h, i, j = heapq.heappop(q)\n",
    "            print(res, h)\n",
    "            res = max(res, h)\n",
    "            if h < res:\n",
    "                ans += (res - h)\n",
    "                heightMap[i][j] = res\n",
    "                \n",
    "            \n",
    "            for (i_, j_) in ((i-1, j),(i, j-1),(i+1, j),(i, j+1)):\n",
    "                if (i_, j_) not in vis:\n",
    "                    vis.add((i_, j_))\n",
    "                    if i_ >=0 and j_ >=0 and i_ < len(heightMap) and j_ < len(heightMap[0]):\n",
    "                        heapq.heappush(q, (heightMap[i_][j_],i_,j_))\n",
    "            \n",
    "        return ans\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trapRainWater(self, heightMap: List[List[int]]) -> int:\n",
    "        def getFa(i) :\n",
    "            if fa[i] == i : return i\n",
    "            fa[i] = getFa(fa[i])\n",
    "            return fa[i]\n",
    "\n",
    "        m = len(heightMap)+2\n",
    "        n = len(heightMap[0])+2\n",
    "        tot = m * n\n",
    "\n",
    "        fa = [-1] * tot\n",
    "        for i in range(m) :\n",
    "            fa[i*n] = fa[(i+1)*n-1] = 0\n",
    "        for i in range(n) :\n",
    "            fa[i] = fa[-1-i] = 0\n",
    "\n",
    "        q = []\n",
    "        i = n-2\n",
    "        for r in heightMap :\n",
    "            i += 2\n",
    "            for j in r :\n",
    "                i += 1\n",
    "                heappush(q, (j, i))\n",
    "\n",
    "        c = Counter()\n",
    "        c[0] = (m+n-2)*2\n",
    "\n",
    "        res = 0\n",
    "        preH = 0\n",
    "        while q :\n",
    "            h, i = heappop(q)\n",
    "            res += (h-preH) * (tot - c[0] - len(q) - 1)\n",
    "            preH = h\n",
    "\n",
    "            fa[i] = i\n",
    "            c[i] = 1\n",
    "\n",
    "            neighbors = {i}\n",
    "            if fa[i-n] >= 0 : neighbors.add(getFa(i-n))\n",
    "            if fa[i+n] >= 0 : neighbors.add(getFa(i+n))\n",
    "            if fa[i-1] >= 0 : neighbors.add(getFa(i-1))\n",
    "            if fa[i+1] >= 0 : neighbors.add(getFa(i+1))\n",
    "            neighbors = list(sorted(neighbors))\n",
    "\n",
    "            i = neighbors[0]\n",
    "            for j in neighbors[1:] :\n",
    "                fa[j] = i\n",
    "                c[i] += c[j]\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trapRainWater(self, heightMap: List[List[int]]) -> int:\n",
    "        from heapq import heappush, heappop\n",
    "        m, n = len(heightMap), len(heightMap[0])\n",
    "        res, q, vis = 0, [], set()\n",
    "        for i in range(m):\n",
    "            for j in [0, n - 1]:\n",
    "                heappush(q, [heightMap[i][j], i, j])\n",
    "                vis.add((i, j))\n",
    "\n",
    "        for j in range(1, n - 1):\n",
    "            for i in [0, m - 1]:\n",
    "                heappush(q, [heightMap[i][j], i, j])\n",
    "                vis.add((i, j))\n",
    "\n",
    "        while q:\n",
    "            h, i, j = heappop(q)\n",
    "            for ni, nj in [[i, j - 1], [i, j + 1], [i - 1, j], [i + 1, j]]:\n",
    "                if 0 <= ni < m and 0 <= nj < n and (ni, nj) not in vis:\n",
    "                    vis.add((ni, nj))\n",
    "                    heappush(q, [max(h, heightMap[ni][nj]), ni, nj])\n",
    "                    res += max(0, h - heightMap[ni][nj])\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trapRainWater(self, heightMap: List[List[int]]) -> int:\n",
    "        m, n = len(heightMap), len(heightMap[0])\n",
    "        if m <= 2 or n <= 2:\n",
    "            return 0\n",
    "        h = []\n",
    "        visited = defaultdict(bool)\n",
    "        # 边缘入堆\n",
    "        for i in range(m):\n",
    "            heappush(h, (heightMap[i][0], i, 0))\n",
    "            heappush(h, (heightMap[i][n - 1], i, n - 1))\n",
    "            visited[(i, 0)] = visited[(i, n - 1)] = True\n",
    "        for j in range(1, n - 1):\n",
    "            heappush(h, (heightMap[0][j], 0, j))\n",
    "            heappush(h, (heightMap[m - 1][j], m - 1, j))\n",
    "            visited[(0, j)] = visited[(m - 1, j)] = True\n",
    "        ans = 0\n",
    "        # 堆里全是围栏\n",
    "        while h:\n",
    "            # 弹出最矮的围栏\n",
    "            t, x, y = heappop(h)\n",
    "            for tx, ty in (\n",
    "                (x, y - 1), (x, y + 1), (x - 1, y), (x + 1, y)\n",
    "            ):\n",
    "                if 0 <= tx < m and 0 <= ty < n and not visited[(tx, ty)]:\n",
    "                    # 比最矮的围栏还矮\n",
    "                    if heightMap[tx][ty] < t:\n",
    "                        ans += t - heightMap[tx][ty]\n",
    "                    heappush(h, (max(t, heightMap[tx][ty]), tx, ty))\n",
    "                    visited[(tx, ty)] = True\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trapRainWater(self, heightMap: List[List[int]]) -> int:\n",
    "        m, n = len(heightMap), len(heightMap[0])\n",
    "        pq = []\n",
    "        vis = set()\n",
    "        # 边界一定无法接雨水\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i == 0 or j == 0 or i == m - 1 or j == n - 1:\n",
    "                    heappush(pq, (heightMap[i][j], i, j))\n",
    "                    vis.add((i, j))\n",
    "        res = 0\n",
    "        # 一维接雨水是左最大值lmax和右最大值rmax两者取最小值，二维和一维也是一样的思路，要用堆模拟\n",
    "        # 当前位置能接的雨水=max(之前得到的高度最大值的最小值-当前位置的高度, 0)\n",
    "        while pq:\n",
    "            h, x, y = heappop(pq)\n",
    "            for nx, ny in (x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1):\n",
    "                if 0 <= nx < m and 0 <= ny < n and (nx, ny) not in vis:\n",
    "                    heappush(pq, (max(h, heightMap[nx][ny]), nx, ny))\n",
    "                    res += max(h - heightMap[nx][ny], 0) \n",
    "                    vis.add((nx, ny))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trapRainWater(self, heightMap: List[List[int]]) -> int:\n",
    "        heap = []\n",
    "        visited = set()\n",
    "        for i, row in enumerate(heightMap):\n",
    "            for j, cell in enumerate(row):\n",
    "                if i == 0 or j == 0 or i == len(heightMap)-1 or j == len(row)-1:\n",
    "                    heapq.heappush(heap, (cell, i, j))\n",
    "                    visited.add((i, j))\n",
    "\n",
    "        result = 0\n",
    "        while heap:\n",
    "            mi, x, y = heapq.heappop(heap)\n",
    "            for di in [[1, 0], [-1, 0], [0, 1], [0, -1]]:\n",
    "                i, j = x+di[0], y+di[1]\n",
    "                if i < 0 or i >= len(heightMap): continue\n",
    "                if j < 0 or j >= len(heightMap[x]): continue\n",
    "                if (i, j) not in visited:\n",
    "                    visited.add((i, j))\n",
    "                    heapq.heappush(heap, (max(mi, heightMap[i][j]), i, j))\n",
    "                    if heightMap[i][j] < mi:\n",
    "                        result += mi - heightMap[i][j]\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trapRainWater(self, heightMap: List[List[int]]) -> int:\n",
    "        m, n = len(heightMap), len(heightMap[0])\n",
    "        pq = []\n",
    "        vis = set()\n",
    "        # 边界一定无法接雨水\n",
    "        for i in range(m):\n",
    "            heappush(pq, (heightMap[i][0], i, 0))\n",
    "            vis.add((i, 0))\n",
    "            heappush(pq, (heightMap[i][n-1], i, n-1))\n",
    "            vis.add((i, n-1))\n",
    "        for j in range(1, n-1):\n",
    "            heappush(pq, (heightMap[0][j], 0, j))\n",
    "            vis.add((0, j))\n",
    "            heappush(pq, (heightMap[m-1][j], m-1, j))\n",
    "            vis.add((m-1, j))\n",
    " \n",
    "        res = 0\n",
    "        # 一维接雨水是左最大值lmax和右最大值rmax两者取最小值，二维和一维也是一样的思路，要用堆模拟\n",
    "        # 当前位置能接的雨水=max(之前得到的高度最大值的最小值-当前位置的高度, 0)\n",
    "        while pq:\n",
    "            h, x, y = heappop(pq)\n",
    "            for nx, ny in (x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1):\n",
    "                if 0 <= nx < m and 0 <= ny < n and (nx, ny) not in vis:\n",
    "                    heappush(pq, (max(h, heightMap[nx][ny]), nx, ny))\n",
    "                    res += max(h - heightMap[nx][ny], 0) \n",
    "                    vis.add((nx, ny))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trapRainWater(self, h: List[List[int]]) -> int:\n",
    "        # 一个格子能接的最大水量取决于四周最低的一个格子高度，边界的格子都接不了水\n",
    "        vis = set()\n",
    "        pq = []\n",
    "        m,n = len(h),len(h[0])\n",
    "        for i,row in enumerate(h):\n",
    "            for j,x in enumerate(row):\n",
    "                if i == 0 or i == m - 1 or j == 0 or j == n - 1:\n",
    "                    heappush(pq,(x,i,j))\n",
    "                    vis.add((i,j))\n",
    "        \n",
    "        ans = 0\n",
    "        while pq:\n",
    "            # 每次从堆里取最低的格子，去更新他的四周格子\n",
    "            x,r,c = heappop(pq)\n",
    "            for nr,nc in (r + 1,c),(r - 1,c),(r,c + 1),(r,c - 1):\n",
    "                if 0 <= nr < m and 0 <= nc < n and (nr,nc) not in vis:\n",
    "                    vis.add((nr,nc))\n",
    "                    if h[nr][nc] >= x:\n",
    "                        # 没法装水\n",
    "                        heappush(pq,(h[nr][nc],nr,nc))\n",
    "                    else:\n",
    "                        # 装到x\n",
    "                        ans += x - h[nr][nc]\n",
    "                        heappush(pq,(x,nr,nc))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trapRainWater(self, heightMap: List[List[int]]) -> int:\n",
    "\n",
    "\n",
    "        n,m = len(heightMap),len(heightMap[0])\n",
    "        if n<=2 or m<=2:\n",
    "            return 0 \n",
    "        \n",
    "        visited =set()\n",
    "        out_layer = []\n",
    "\n",
    "        for i in range(n):\n",
    "            heapq.heappush(out_layer,(heightMap[i][0], i,0 ))\n",
    "            visited.add((i,0))\n",
    "            heapq.heappush(out_layer,(heightMap[i][m-1], i,m-1 ))\n",
    "            visited.add((i,m-1))\n",
    "        for j in range(1,m-1):\n",
    "            heapq.heappush(out_layer,(heightMap[0][j], 0,j ))\n",
    "            visited.add((0,j))\n",
    "            heapq.heappush(out_layer,(heightMap[n-1][j], n-1,j ))\n",
    "            visited.add( (n-1,j) )\n",
    "\n",
    "        sums = 0 \n",
    "        while out_layer:\n",
    "            h,i,j = heapq.heappop(out_layer)\n",
    "            for dx,dy in [(-1,0),(1,0),(0,1),(0,-1)]:\n",
    "                x,y = i+dx,j+dy \n",
    "                if 0<=x<n and 0<=y<m and (x,y) not in visited:\n",
    "                    water = max(h,heightMap[x][y])\n",
    "                    sums += water-heightMap[x][y]\n",
    "                    heapq.heappush(out_layer,(water,x,y))\n",
    "                    visited.add((x,y))\n",
    "        return sums \n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height: List[int]) -> int:\n",
    "        depth = 0\n",
    "        size = len(height)\n",
    "        highestRight = [0 for _ in range(size)]\n",
    "        highestLeft = [0 for _ in range(size)]\n",
    "        \n",
    "        for i in range(size-2, -1, -1):\n",
    "            highestRight[i] = max(highestRight[i+1], height[i+1])\n",
    "            \n",
    "        for i in range(1, size):\n",
    "            highestLeft[i] = max(highestLeft[i-1], height[i-1])\n",
    "            depth += max(0, min(highestLeft[i], highestRight[i]) - height[i])\n",
    "            \n",
    "        return depth"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height):\n",
    "        \"\"\"\n",
    "        :type height: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        maxH = 0\n",
    "        for i in range(len(height)):\n",
    "            maxH = max(maxH, height[i])\n",
    "        \n",
    "        volume = maxH * len(height)\n",
    "        for i in height:\n",
    "            volume -= i\n",
    "        currentH = 1\n",
    "        for i in range(len(height)):\n",
    "            while height[i] >= currentH:\n",
    "                volume -= i\n",
    "                currentH += 1\n",
    "            if currentH > maxH:\n",
    "                break\n",
    "        currentH = 1\n",
    "        for i in range(len(height) - 1, -1, -1):\n",
    "            while height[i] >= currentH:\n",
    "                volume -= (len(height) - 1 - i)\n",
    "                currentH += 1\n",
    "            if currentH > maxH:\n",
    "                break\n",
    "        return volume"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height):\n",
    "        \"\"\"\n",
    "        :type height: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        water = 0\n",
    "        n = len(height)\n",
    "        l, r = 0, n - 1\n",
    "        max_l, max_r = 0, 0\n",
    "        while l <= r:\n",
    "            max_l = max(max_l, height[l])\n",
    "            max_r = max(max_r, height[r])\n",
    "            if max_l <= max_r:\n",
    "                water += max_l - height[l]\n",
    "                l += 1\n",
    "            else:\n",
    "                water += max_r - height[r]\n",
    "                r -= 1\n",
    "\n",
    "        return water\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height: 'List[int]') -> 'int':\n",
    "        \n",
    "        _height = height[1:-1]\n",
    "        if not _height:\n",
    "            return 0\n",
    "        \n",
    "        hmax = max(_height)\n",
    "        hmin = min(height[0], height[-1])\n",
    "        \n",
    "        if hmax < hmin:\n",
    "            return hmin * len(_height) - sum(_height)\n",
    "        \n",
    "        pos = _height.index(hmax) + 1\n",
    "        return self.trap(height[:pos+1]) + self.trap(height[pos:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height):\n",
    "        \"\"\"\n",
    "        :type height: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        self.vol = 0\n",
    "        self.hole_list = []\n",
    "        i = 0\n",
    "        while True:\n",
    "            if i >= len(height)-1:\n",
    "                break\n",
    "            start_pos, end_pos = self.find_hole(height[i:])\n",
    "            if start_pos == -1:\n",
    "                return self.vol\n",
    "            elif end_pos == -1:\n",
    "                i += 1\n",
    "                continue\n",
    "            else:\n",
    "                start_pos += i\n",
    "                end_pos += i\n",
    "                self.vol += self.count_water(height[start_pos:end_pos + 1])\n",
    "                i = end_pos\n",
    "        return self.vol\n",
    "\n",
    "    def count_water(self, height):\n",
    "        count = 0\n",
    "        if len(height) == 0:\n",
    "            return count\n",
    "        first_high = height[0]\n",
    "        last_high = height[-1]\n",
    "        if first_high >= last_high:\n",
    "            second_high = last_high\n",
    "        else:\n",
    "            second_high = first_high\n",
    "        for i in range(1,len(height)):\n",
    "            minus = second_high - height[i]\n",
    "            if minus > 0:\n",
    "                count += minus\n",
    "        return count\n",
    "\n",
    "    def find_hole(self, height):\n",
    "        start_pos = -1\n",
    "        end_pos = -1\n",
    "        second_high = 0\n",
    "        for i in range(1,len(height)):\n",
    "            if height[i] < height[i-1]:\n",
    "                start_pos = i-1\n",
    "                for j in range(i+1,len(height)):\n",
    "\n",
    "                    if height[j] >= height[start_pos]:\n",
    "                        end_pos = j\n",
    "                        break\n",
    "                    else:\n",
    "                        if height[j] > second_high:\n",
    "                            second_high = height[j]\n",
    "                            end_pos = j\n",
    "                break\n",
    "        return start_pos, end_pos"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height: List[int]) -> int:\n",
    "        if len(height) < 2:\n",
    "            return 0\n",
    "        result = 0\n",
    "        l = 0\n",
    "        r = len(height) - 1\n",
    "        heighter = 0\n",
    "        while l <= r:\n",
    "            if min(height[l], height[r]) > heighter:\n",
    "                result += (r - l + 1) * (min(height[l], height[r]) - heighter)\n",
    "                heighter = min(height[l], height[r])\n",
    "            if height[l] < height[r]:\n",
    "                l += 1\n",
    "            else:\n",
    "                r -= 1\n",
    "        return result - sum(height)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height: List[int]) -> int:\n",
    "        if len(height) <= 2: return 0\n",
    "        bit = [(0, height[0])] if height[0] > height[1] else []\n",
    "        for i in range(1, len(height) - 1):\n",
    "            if height[i] >= height[i-1] and height[i] >= height[i+1]:\n",
    "                bit.append((i, height[i]))\n",
    "        if height[-1] > height[-2]:\n",
    "            bit += [(len(height) - 1, height[-1])]\n",
    "        if len(bit) <= 1:\n",
    "            return 0\n",
    "        area = 0\n",
    "        i = 0\n",
    "        while i < len(bit) - 1:\n",
    "            m = bit[i][1]\n",
    "            for j in range(i+1, len(bit)):\n",
    "                if bit[j][1] >= m:\n",
    "                    break\n",
    "            if j >= len(bit) - 1:\n",
    "                k = max(enumerate(bit[i+1:]), key=lambda x: x[1][1])\n",
    "                j = k[0] + i + 1\n",
    "                k = k[1][0]\n",
    "            else:\n",
    "                k = bit[j][0]\n",
    "            edge = min(m, height[k])\n",
    "            area += (k - bit[i][0] - 1)*edge\n",
    "            for x in height[bit[i][0]+1: k]:\n",
    "                area -= min(edge, x)\n",
    "            i = j\n",
    "        return area\n",
    "                \n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height):\n",
    "        if not height:\n",
    "            return 0\n",
    "\n",
    "        water = 0\n",
    "        left, right = 0, len(height)-1\n",
    "        max_left, max_right = height[0], height[len(height)-1]\n",
    "\n",
    "        while left < right - 1:\n",
    "            # If the left building is taller,\n",
    "            if height[left] < height[right]:\n",
    "                left += 1\n",
    "                max_left = max(max_left, height[left])\n",
    "\n",
    "                if height[left] < max_right:\n",
    "                    water += max_left - height[left]\n",
    "\n",
    "            else:\n",
    "                right -= 1\n",
    "                max_right = max(max_right, height[right])\n",
    "\n",
    "                if height[right] < max_left:\n",
    "                    water += max_right - height[right]\n",
    "\n",
    "        return water"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height):\n",
    "        \"\"\"\n",
    "        :type height: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if len(height) == 0:\n",
    "            return 0\n",
    "        sum1 = 0\n",
    "        sum2 = 0\n",
    "        max1 = 0\n",
    "        for i in height:\n",
    "            if i > max1:\n",
    "                max1 = i\n",
    "        index = height.index(max1)\n",
    "        max1 = 0\n",
    "        for i in range(index):\n",
    "            if i == 0:\n",
    "                max1 = i\n",
    "            else:\n",
    "                if height[i] < height[max1]:\n",
    "                    s = height[max1] -height[i]\n",
    "                    sum1 += s\n",
    "                elif height[i] > height[max1]:\n",
    "                    max1 = i\n",
    "        max2 = 0\n",
    "        for k in range(len(height)-1,index,-1):\n",
    "            if k == len(height)-1:\n",
    "                max2 = k\n",
    "            else:\n",
    "                if height[k] < height[max2]:\n",
    "                    s = height[max2] -height[k]\n",
    "                    sum2 += s\n",
    "                elif height[k] > height[max2]:\n",
    "                    max2 = k\n",
    "        return sum1 + sum2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, h):\n",
    "        \"\"\"\n",
    "        :type height: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        n = len(h)\n",
    "        max_lh, max_rh = [0]*(n+1), [0]*(n+1)\n",
    "        for i, x in enumerate(h): max_lh[i] = max(max_lh[i-1], x)\n",
    "        for i, x in reversed(list(enumerate(h))): max_rh[i] = max(max_rh[i+1], x)     \n",
    "        ans = 0\n",
    "        for i, x in enumerate(h): ans += max(0, min(max_lh[i], max_rh[i]) - x)            \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def trap(self, height):\n",
    "        \"\"\"\n",
    "        :type height: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if not height or len(height) < 2:\n",
    "            return 0\n",
    "        hlen = len(height)\n",
    "        lmax = [0] * hlen\n",
    "        rmax = [0] * hlen\n",
    "        tmp_max = height[0]\n",
    "        for i in range(hlen):\n",
    "            if tmp_max < height[i]:\n",
    "                tmp_max = height[i]\n",
    "            lmax[i] = tmp_max\n",
    "        tmp_max = height[hlen-1]\n",
    "        for i in range(hlen - 1, -1, -1):\n",
    "            if tmp_max < height[i]:\n",
    "                tmp_max = height[i]\n",
    "            rmax[i] = tmp_max\n",
    "        tmp_sum = 0\n",
    "        for i in range(hlen):\n",
    "            tmp_sum += min(lmax[i], rmax[i]) - height[i]\n",
    "        return tmp_sum\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height):\n",
    "\n",
    "        if len(height) <= 2:\n",
    "            return 0\n",
    "\n",
    "        maxrs = [0]*(len(height)+1)\n",
    "        for i in range(len(height)):\n",
    "            ri = len(height)-i-1\n",
    "            maxrs[ri] = max(height[ri], maxrs[ri+1])\n",
    "\n",
    "        maxl, sumw = 0, 0\n",
    "        for i in range(len(height)):\n",
    "            maxl = max(maxl, height[i])\n",
    "            sumw += max(min(maxl, maxrs[i]) - height[i], 0)\n",
    "\n",
    "        return sumw"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height):\n",
    "        \"\"\"\n",
    "        :type height: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        res = 0\n",
    "        if not height:\n",
    "            return res\n",
    "        position = [(x, height[x]) for x in range(len(height))]\n",
    "        positionSort = sorted(position, key=lambda x: x[1], reverse=True)\n",
    "        position = [position for position, height in positionSort]\n",
    "        height = [height for position, height in positionSort]\n",
    "        fast = 0\n",
    "        slow = 0\n",
    "        temp = []\n",
    "        while fast != len(height) and height[slow] != 0:\n",
    "            fast += 1\n",
    "            if fast == len(height) or height[fast] != height[slow]:\n",
    "                temp.append((height[slow],(min(position[slow:fast]), max(position[slow:fast]))))\n",
    "                slow = fast\n",
    "        value, (slow, fast) = temp[0] if temp else (0, (0, 0))\n",
    "        res += value * (fast - slow + 1)\n",
    "        for x in temp:\n",
    "            if x[1][1] > fast:\n",
    "                res += x[0] * (x[1][1] - fast)\n",
    "                fast = x[1][1]\n",
    "            if x[1][0] < slow:\n",
    "                res += x[0] * (slow - x[1][0])\n",
    "                slow = x[1][0]\n",
    "        return res - sum(height)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height):\n",
    "        \"\"\"\n",
    "        :type height: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        res = 0\n",
    "        if not height:\n",
    "            return res\n",
    "        position = [(x, height[x]) for x in range(len(height))]\n",
    "        positionSort = sorted(position, key=lambda x: x[1], reverse=True)\n",
    "        position = [position for position, height in positionSort]\n",
    "        height = [height for position, height in positionSort]\n",
    "        fast = 0\n",
    "        slow = 0\n",
    "        temp = []\n",
    "        while fast != len(height) and height[slow] != 0:\n",
    "            fast += 1\n",
    "            if fast == len(height) or height[fast] != height[slow]:\n",
    "                temp.append((height[slow],(min(position[slow:fast]), max(position[slow:fast]))))\n",
    "                slow = fast\n",
    "        value, (slow, fast) = temp[0] if temp else (0, (0, 0))\n",
    "        res += value * (fast - slow + 1)\n",
    "        for x in temp:\n",
    "            if x[1][1] > fast:\n",
    "                res += x[0] * (x[1][1] - fast)\n",
    "                fast = x[1][1]\n",
    "            if x[1][0] < slow:\n",
    "                res += x[0] * (slow - x[1][0])\n",
    "                slow = x[1][0]\n",
    "        return res - sum(height)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height):\n",
    "        \"\"\"\n",
    "        :type height: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if not height:\n",
    "            return 0\n",
    "        l_max, r_max, area = 0, 0, 0\n",
    "        l_index, r_index = 0, len(height) - 1\n",
    "        while l_index < r_index:\n",
    "            l_max = max(l_max, height[l_index])\n",
    "            r_max = max(r_max, height[r_index])\n",
    "            if l_max < r_max:\n",
    "                area = area + l_max - height[l_index]\n",
    "                l_index +=1\n",
    "            else:\n",
    "                area = area + r_max - height[r_index]\n",
    "                r_index -= 1\n",
    "        return area\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height: 'List[int]') -> 'int':\n",
    "        L = len(height)\n",
    "        if L == 0:\n",
    "            return 0\n",
    "        area = 0\n",
    "        left_max = [0 for i in range(L)]\n",
    "        right_max = [0 for j in range(L)]\n",
    "        left_max[0] = height[0]\n",
    "        for i in range(1, L):\n",
    "            left_max[i] = max(left_max[i - 1], height[i])\n",
    "        right_max[L - 1] = height[L - 1]\n",
    "        i = L - 2\n",
    "        while i >= 0:\n",
    "            right_max[i] = max(right_max[i + 1], height[i])\n",
    "            i -= 1\n",
    "        for i in range(1, L):\n",
    "            area += min(left_max[i], right_max[i]) - height[i]\n",
    "        return area\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height: 'List[int]') -> 'int':\n",
    "            height1, left, right, water = [], 0, 0, 0\n",
    "            for i in height:\n",
    "                left = max(left, i)\n",
    "                height1.append(left)\n",
    "            height1.reverse()\n",
    "            for n, i in enumerate(reversed(height)):\n",
    "                right = max(right, i)\n",
    "                water += min(height1[n], right) - i\n",
    "            return water\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height: List[int]) -> int:\n",
    "        if not height: return 0\n",
    "        n = len(height)\n",
    "        stack = []\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            #print(stack)\n",
    "            while stack and height[stack[-1]] < height[i]:\n",
    "                tmp = stack.pop()\n",
    "                if not stack: break\n",
    "                res += (min(height[i], height[stack[-1]]) - height[tmp]) * (i-stack[-1] - 1)\n",
    "            stack.append(i)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height: List[int]) -> int:\n",
    "        stack=[]\n",
    "        total=0\n",
    "        for i in range(len(height)):\n",
    "            while(len(stack)!=0 and height[stack[-1]]<=height[i]):\n",
    "                a=stack.pop(-1)\n",
    "                if len(stack)==0:\n",
    "                    break\n",
    "                h=min(height[stack[-1]],height[i])-height[a]\n",
    "                dist=i-stack[-1]-1\n",
    "                total+=h*dist\n",
    "            stack.append(i)\n",
    "        return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height):\n",
    "        n = len(height)\n",
    "        rain_cap = 0\n",
    "        i = 1\n",
    "        while i < n-1:\n",
    "            if max(height[:i]) <= height[i] or height[i] >= max(height[i+1:]):\n",
    "                i += 1\n",
    "                continue\n",
    "            else:\n",
    "                left = i - 1\n",
    "                right = i + 1\n",
    "                while right < n and height[right] <= height[i] or (height[right] < max(height[right:]) and height[left] > height[right]):\n",
    "                    right += 1\n",
    "                all_cap = (right - left - 1) * min(height[left],height[right])\n",
    "                pillar_cap = sum(height[left + 1:right])\n",
    "                rain_cap += all_cap - pillar_cap\n",
    "                i = right\n",
    "        return rain_cap"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height: List[int]) -> int:\n",
    "        n=len(height)\n",
    "        res=0\n",
    "        left,right=0,n-1\n",
    "        left_max,right_max=0,0\n",
    "        while left<right:\n",
    "            if height[left]<height[right]:\n",
    "                if height[left]>=left_max:\n",
    "                    left_max=height[left]\n",
    "                else:\n",
    "                    res+=left_max-height[left]\n",
    "                left+=1\n",
    "\n",
    "            else:\n",
    "                if height[right]>=right_max:\n",
    "                    right_max=height[right]\n",
    "                else:\n",
    "                    res+=right_max-height[right]\n",
    "                right-=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height: List[int]) -> int:\n",
    "        stack = list()\n",
    "        rain = 0\n",
    "        left = 0\n",
    "        for item in height:\n",
    "            if item > left:\n",
    "                while stack:\n",
    "                    v = stack.pop()\n",
    "                    rain = rain + left - v\n",
    "                left = item\n",
    "            stack.append(item)\n",
    "        right = 0\n",
    "        while stack:\n",
    "            v = stack.pop()\n",
    "            right = max(right, v)\n",
    "            rain = rain + right - v\n",
    "        return rain\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height: List[int]) -> int:\n",
    "        def force(height):\n",
    "            N = len(height)\n",
    "            res = 0\n",
    "            for i in range(1, N - 1):\n",
    "                leftMax = max(height[0 : i])\n",
    "                rightMax = max(height[i + 1 : N])\n",
    "                if height[i] < leftMax and height[i] < rightMax:\n",
    "                    res += min(leftMax, rightMax) - height[i]\n",
    "            return res\n",
    "\n",
    "        return force(height)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height: List[int]) -> int:\n",
    "        l = 0\n",
    "        r = len(height) - 1\n",
    "        ans = 0\n",
    "        left_max = 0\n",
    "        right_max = 0\n",
    "        while l <= r:##注意这里要有等号\n",
    "            if left_max < right_max:\n",
    "                ans += max(0, left_max - height[l])\n",
    "                left_max = max(left_max, height[l])\n",
    "                l += 1\n",
    "            else:\n",
    "                ans += max(0, right_max - height[r])\n",
    "                right_max = max(right_max, height[r])\n",
    "                r -= 1\n",
    "        \n",
    "        return  ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height: List[int]) -> int:\n",
    "        water = []\n",
    "        # if height[0] == 0:\n",
    "        #     water.append(0)\n",
    "        # else:\n",
    "        #     sub = height[1] - height[0]\n",
    "        #     startWater = sub if sub >=0 else 0\n",
    "        #     water.append(startWater)\n",
    "        i = 1\n",
    "        while i < len(height) - 1:\n",
    "            colWater = min(max(height[:i]), max(height[i+1:]))\n",
    "            if colWater >= height[i]:\n",
    "                colWater = colWater - height[i]\n",
    "            else:\n",
    "                colWater = 0\n",
    "            water.append(colWater)\n",
    "            i += 1\n",
    "        # if height[-1] != 0:\n",
    "        #     sub = height[-2] - height[-1]\n",
    "        #     endWater = sub if sub >=0 else 0\n",
    "        #     water.append(endWater)\n",
    "        return sum(water)\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height: List[int]) -> int:\n",
    "        l = len(height)\n",
    "        d = [0 for _ in range(l)]\n",
    "        dp1 = height.copy()\n",
    "        dp2 = height.copy()\n",
    "        for i in range(1, len(height)):\n",
    "            if height[i] <= dp1[i-1]:\n",
    "                dp1[i] = dp1[i-1] \n",
    "        print(dp1)\n",
    "        for i in range(l-2, 0, -1):\n",
    "            #print(i, height[i], dp2[i+1])\n",
    "            if height[i] <= dp2[i+1]:\n",
    "                dp2[i] = dp2[i+1]\n",
    "        print(dp2)\n",
    "        for i in range(len(height)):\n",
    "            l_height = 0 if i == 0 else dp1[i-1]\n",
    "            r_height = 0 if i == len(height) - 1 else dp2[i+1]\n",
    "            if l_height <= height[i] or r_height<=height[i]:\n",
    "                d[i] = 0 \n",
    "            else:\n",
    "                d[i] = min(r_height-height[i], l_height-height[i])\n",
    "        return sum(d)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def trap(self, height):\n",
    "        \"\"\"\n",
    "        :type height: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        stack = []           \n",
    "        res = 0\n",
    "        for i in range(len(height)):\n",
    "            while stack and height[i] > height[stack[-1]]: \n",
    "                top = stack.pop()\n",
    "                if not stack: break          \n",
    "                res += (i - stack[-1] - 1) * (min(height[i], height[stack[-1]]) - height[top])\n",
    "            stack.append(i)          \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height: List[int]) -> int:\n",
    "        res = 0\n",
    "        for i in range(1,len(height)-1):\n",
    "            left = max(height[0:i])\n",
    "            right = max(height[i:len(height)])\n",
    "            res += max( min(left,right) - height[i] , 0)\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height: List[int]) -> int:\n",
    "        stack = []\n",
    "        res = 0\n",
    "        for i in range(len(height)):\n",
    "            while stack and height[stack[-1]]<height[i]:\n",
    "                tem = stack.pop()\n",
    "                if not stack:\n",
    "                    break\n",
    "                h = min(height[i],height[stack[-1]]) - height[tem]\n",
    "                res += (i-stack[-1]-1)*h\n",
    "            stack.append(i)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height):\n",
    "        n = len(height)\n",
    "        l = 0\n",
    "        r = n - 1\n",
    "        rain = 0\n",
    "        if n < 3: return rain\n",
    "        else:\n",
    "            while r - l > 1:\n",
    "                ridge = min(height[l], height[r])\n",
    "                for i in range(l+1,r):\n",
    "                    if height[i] < ridge:\n",
    "                        rain += (ridge - height[i])\n",
    "                        height[i] = ridge\n",
    "                if height[l] <= height[r]: l += 1\n",
    "                else: r -= 1\n",
    "            print(height)\n",
    "            return rain"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height: List[int]) -> int:\n",
    "        if height == sorted(height):return 0\n",
    "        i,j= 0,len(height)-1\n",
    "        res = 0\n",
    "        while i<j:\n",
    "            if height[i] !=0 and height[j] != 0:\n",
    "                for k in range(i+1,j):\n",
    "                    a = min(height[i],height[j])\n",
    "                    if height[k] < a:\n",
    "                        res += a-height[k]\n",
    "                        height[k] = a\n",
    "            if height[i] < height[j]:\n",
    "                i +=1\n",
    "            elif height[i] >= height[j]:\n",
    "                j -=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height: List[int]) -> int:\n",
    "        left, right = 0, len(height) - 1\n",
    "        left_max, right_max = 0, 0\n",
    "        res = 0\n",
    "        while left <= right:\n",
    "            if left_max < right_max:\n",
    "                left_max = max(left_max, height[left])\n",
    "                res += left_max - height[left]\n",
    "                left += 1\n",
    "            else:\n",
    "                right_max = max(right_max, height[right])\n",
    "                res += right_max - height[right]\n",
    "                right -= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height: List[int]) -> int:\n",
    "        n = len(height)\n",
    "\n",
    "        pre_max = [height[0]] * n\n",
    "        for i in range(1, n):\n",
    "            pre_max[i] = max(pre_max[i-1], height[i])\n",
    "\n",
    "        suf_max = [height[-1]] * n\n",
    "        for i in range(n-2, -1, -1):\n",
    "            suf_max[i] = max(suf_max[i+1], height[i])\n",
    "\n",
    "        ans = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            h = height[i]\n",
    "            pre_h = pre_max[i]\n",
    "            suf_h = suf_max[i]\n",
    "            \n",
    "            ans += min(pre_h, suf_h) - h\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height: List[int]) -> int:\n",
    "        # 单调栈问题\n",
    "        # 预处理出来左边最大值和右边最大值\n",
    "        n = len(height)\n",
    "        r = [0] * n\n",
    "        mx = 0\n",
    "        for i in range(n-1, -1, -1):\n",
    "            mx = max(mx, height[i])\n",
    "            r[i] = mx\n",
    "        ans = 0\n",
    "        mx = 0\n",
    "        for i in range(n):\n",
    "            mx = max(mx, height[i])\n",
    "            ans += (max(0, min(mx, r[i]) - height[i]))\n",
    "        # ans = 0\n",
    "        # for i in range(n):\n",
    "        #     ans += (max(0, min(l[i], r[i]) - height[i]))\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height: List[int]) -> int:\n",
    "        left = 0\n",
    "        right = len(height) - 1\n",
    "        left_max = right_max = ans = 0\n",
    "    \n",
    "        while left < right:\n",
    "            if height[left] < height[right]:\n",
    "                if height[left] >= left_max:\n",
    "                    left_max = height[left]\n",
    "                else:\n",
    "                    ans += left_max - height[left]\n",
    "                left += 1\n",
    "            else:\n",
    "                if height[right] >= right_max:\n",
    "                    right_max = height[right]\n",
    "                else:\n",
    "                    ans += right_max - height[right]\n",
    "                right -= 1\n",
    "    \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height: List[int]) -> int:\n",
    "        n = len(height)\n",
    "        fi=[0]*n\n",
    "        fi[0]=height[0]\n",
    "        for i in range(1,n):\n",
    "            fi[i]=max(height[i],fi[i-1])\n",
    "        we=[0]*n\n",
    "        we[-1]=height[-1]\n",
    "        for i in range(n-2,-1,-1):\n",
    "            we[i]=max(height[i],we[i+1])\n",
    "        ans=0\n",
    "        for i,j,k in zip(fi,we,height):\n",
    "            ans+=min(j,i)-k\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height: List[int]) -> int:\n",
    "        n = len(height)\n",
    "        left = [0] * n\n",
    "        right = [0] * n\n",
    "        left[0] = height[0]\n",
    "        for i in range(1, n):\n",
    "            left[i] = max(left[i-1], height[i])\n",
    "        right[n-1] = height[n-1]\n",
    "        for i in range(n-2, -1, -1):\n",
    "            right[i] = max(right[i+1], height[i])\n",
    "        ret = 0\n",
    "        for i in range(n):\n",
    "            ret += min(right[i], left[i]) - height[i]\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height: List[int]) -> int:\n",
    "        if not height:\n",
    "            return 0\n",
    "\n",
    "        n = len(height)\n",
    "        left, right = 0, n - 1\n",
    "        left_max, right_max = height[left], height[right]\n",
    "        trapped_water = 0\n",
    "\n",
    "        while left < right:\n",
    "            if left_max < right_max:\n",
    "                left += 1\n",
    "                left_max = max(left_max, height[left])\n",
    "                trapped_water += left_max - height[left]\n",
    "            else:\n",
    "                right -= 1\n",
    "                right_max = max(right_max, height[right])\n",
    "                trapped_water += right_max - height[right]\n",
    "\n",
    "        return trapped_water\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height: List[int]) -> int:\n",
    "        ans = 0\n",
    "        stk = []\n",
    "        for i, h in enumerate(height):\n",
    "            while stk and h > height[stk[-1]]:\n",
    "                cur_h = height[stk.pop()]\n",
    "                if not stk:\n",
    "                    break\n",
    "                left_h = height[stk[-1]]\n",
    "                ans += (min(left_h, h) - cur_h) * (i - stk[-1] - 1)\n",
    "            stk.append(i)\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height: List[int]) -> int:\n",
    "        n = len(height)\n",
    "        left, right = 0, n-1\n",
    "        maxLeft, maxRight = height[left], height[right]\n",
    "        ans = 0\n",
    "        while left <= right: \n",
    "            maxLeft = max(maxLeft, height[left])\n",
    "            maxRight = max(maxRight, height[right])\n",
    "            if maxLeft < maxRight:\n",
    "                ans += maxLeft - height[left]\n",
    "                left += 1\n",
    "            else:\n",
    "                ans += maxRight - height[right]\n",
    "                right -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height: List[int]) -> int:\n",
    "        n = len(height)\n",
    "        left, right = 0, n-1 \n",
    "        maxLeft, maxRight = height[0], height[n-1]\n",
    "        ans = 0 \n",
    "        while left <= right:\n",
    "            maxLeft = max(maxLeft, height[left])\n",
    "            maxRight = max(maxRight, height[right])\n",
    "            if maxLeft < maxRight:\n",
    "                ans += maxLeft - height[left]\n",
    "                left += 1\n",
    "            else:\n",
    "                ans += maxRight - height[right]\n",
    "                right -= 1 \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height: List[int]) -> int:\n",
    "        # 可以分为按行求或者按列求\n",
    "        if not height or len(height) < 3:\n",
    "            return 0\n",
    "        \n",
    "        sum = 0\n",
    "        # 动规求的左边的最大值和右边的最大值\n",
    "        leftmax = [0]*len(height)\n",
    "        leftmax[0] = height[0]\n",
    "        rightmax = [0]*len(height)\n",
    "        rightmax[-1] = height[-1]\n",
    "        for i in range(1, len(height)):\n",
    "            leftmax[i] = max(leftmax[i-1], height[i])\n",
    "        for i in range(len(height)-2, -1, -1):\n",
    "            rightmax[i] = max(rightmax[i+1], height[i])\n",
    "        \n",
    "        # 遍历按列计算\n",
    "        for i in range(1, len(height)-1):  # 按列进行计算，第一根和最后一根不会有雨水\n",
    "            minheight = min(leftmax[i], rightmax[i])\n",
    "            if minheight > height[i]:\n",
    "                sum += minheight-height[i]\n",
    "        return sum\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
